LINUX.ORG.RU

<kz, что я написал!

Мне нужен алгоритм поиска кратчайшего покрытия.

bk_ ★★
() автор топика
Ответ на: комментарий от pseudo-cat

Честно говоря, не знаю. Скорее всего нет, так как если бы это был он, я бы знал.

Моя задача такова: есть n чисел, на каждой позиции которых может стоять 1, 0 или Х (неопределенность). Нужно из этих n-чисел найти минимальное (кратчайшее) покрытие.

bk_ ★★
() автор топика
Ответ на: комментарий от bk_

Решаю задачу кодирования внутренних состояний асинхронного автомата с устранением опасных состязаний, остался последний шаг из семи - надо найти кратчайшее покрытие.

Писать что-ли тупорылый перебор?

bk_ ★★
() автор топика
Ответ на: комментарий от bk_

Про Х (неопределенность) я соврал. У меня только 0 и 1, то есть битовые маски.

bk_ ★★
() автор топика
Ответ на: комментарий от bk_

> Моя задача такова: есть n чисел, на каждой позиции которых может стоять 1, 0 или Х (неопределенность). Нужно из этих n-чисел найти минимальное (кратчайшее) покрытие.
А можно для неосиляторов теории автоматов рассказать, что вы называете кратчайшим покрытием?

metar ★★★
()
Ответ на: комментарий от metar

Дизьюнкция этих покрытий должна давать 1. А самих покрытий в дизьюнкции должно быть как можно меньше. Вот и вся задача.

bk_ ★★
() автор топика
Ответ на: комментарий от bk_

FIXED

Дизьюнкция этих импликаций должна давать 1. А самих импликаций в дизьюнкции должно быть как можно меньше. Вот и вся задача.

bk_ ★★
() автор топика
Ответ на: комментарий от bk_

о, писал почти то же самое. вы можете задавать состояния автомата как хотите, в смысле в любом удобном виде, а алгоритм который вам нужен это, походу, метод Квайна-Мак-Класски. Кстати, странно, что это последний шаг, а вы о нём не знаете

pseudo-cat ★★★
()
Ответ на: комментарий от pseudo-cat

Вы хотите сказать, что эта задача сводится к минимизации булевых функций? А там уже метод Мак-Класски или Карно - уже неважно.

bk_ ★★
() автор топика
Ответ на: комментарий от bk_

Дизьюнкция этих покрытий должна давать 1. А самих покрытий в дизьюнкции должно быть как можно меньше. Вот и вся задача.

слово «покрытий» замените на «конъюнкций» , а чем дизъюнкция конъюнкций не булевая ф-ция. хотя может я вас не так понял.

правда забавно, что полностью с такой задачей кто-то столкнулся кроме меня и решил писать решение на лиспе) я свой код лучше предлагать не буду, он неочень, но отрабатывает, правда помнится столкнулся с неэффективностью этого алгоритма(и не удивительно=)). Я так и не смог посчитать все ф-ции своего задания, но огромный размер моих ф-ций и всего 512мб озу, реабилитирует сам алгоритм)

pseudo-cat ★★★
()
Ответ на: комментарий от pseudo-cat

Если Вам будет интересно, после четверга покажу исходники.

А ваш код, если возможно, конечно, дайте пожалуйста. Лучше что-то, чем ничего.

bk_ ★★
() автор топика
Ответ на: комментарий от bk_

http://www.easy-share.com/1910458577/dy-project.tar.bz2

она ещё умела элементарные логические схемы строить в gschem для полученного автомата, правда я уже не помню как её юзать и разбираться лень) возможно будь время и смысл написал бы её с нуля нормально, а то, когда я ею занимался, опыта лиспа было около нуля, отсюда и не результат

pseudo-cat ★★★
()
Ответ на: комментарий от pseudo-cat

Спасибо, буду смотреть.

bk_ ★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.