|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
07.04.2013, 00:28 | #1 |
Новичок
Джуниор
Регистрация: 07.04.2013
Сообщений: 1
|
Коммивояжер полным перебором
Здравствуйте, помогите разобраться.
Стандартная задача про коммивояжера, правда решить необходимо полным перебором. Коммивояжер хочет объехать N городов и затем вернуться в начальный город,расстояния между которыми заданы. При этом желательно сделать это по наиболее короткому пути (т.к. коммивояжер не располагает лишними средствами на излишние перемещения между городами). Данные ввела в стрингрид, правда, теперь запарялась с прямым перебором, не могу понять, как организовать перебор, чтоб города не повторялись? |
07.04.2013, 14:56 | #2 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Перебор - рекурсией. Учитывая, что задача решается полным перебором, рекурсия не может быть особенно глубокой.
В вызываемую подпрограмму передается массив уже "использованных" городов. Таким образом, глубина стека O(n^2), но для NP-полной задачи n вряд ли будет превосходить 20. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
коммивояжер перебором (delphi) | kokadyyyyyyy | Помощь студентам | 1 | 19.11.2012 18:19 |
Delphi. Жадный алгоритм. Коммивояжер | ZidanCo | Общие вопросы Delphi | 1 | 07.03.2012 10:29 |
Коммивояжер в делфи( | LeToR | Помощь студентам | 0 | 24.12.2011 08:33 |
Коммивояжер | VaSS | Помощь студентам | 0 | 04.05.2010 21:44 |
Объяснение к задаче коммивояжер. | enik pi | Помощь студентам | 2 | 14.06.2007 00:54 |