Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Задача коммивояжера

Автор: LOVE133 3.10.2007 18:53

Все нужные темы закрыты, а новую создавать -мусорить понапрасну.Пишу здесь.Все таже задача коммивояжера, метод ветвей и границ.Но етсь одно но - использование стека.Как и куда его можно там запихнуть?

М
Лучше всегда открывать новую тему - мусор, если что, уберут. П.6: "одна тема - один вопрос"


Автор: Michael_Rybak 3.10.2007 19:45

Обычная реализация - рекурсивная: начинаем в какой-то точке, отмечаем, что мы в ней были, выбираем куда идти и рекурсивно делаем то же самое. Тебе нужно сделать это же, но заменив рекурсию итерациями - как раз с помощью стека.

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