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

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

алгоритм Дейкстры?

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

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

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

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

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

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

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

FIXED

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

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

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

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

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

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

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

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

Кстати, тут вспомнил, что для минимизации булевых функций юзал программу espresso.

http://diamond.gem.valpo.edu/~dhart/ece110/espresso/tutorial.html

Наверное, сейчас ей и воспользуюсь.

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

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

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