Задача коммивояжера
Категория реферата: Рефераты по экономике
Теги реферата: конспект по русскому, титульный лист реферата
Добавил(а) на сайт: Jarkin.
Предыдущая страница реферата | 2 3 4 5 6 7 8 9 10 11 12 | Следующая страница реферата
Нужно понимать, что в ЗК с n городами не нужны все перестановки из n элементов. Потому что перестановки, скажем, 1-3-5-4-2 и 3-5-4-2-1 (последний элемент соединен с первым) задают один и тот же тур, считанный сперва с города 1, а потом с города 3. Поэтому нужно зафиксировать начальный город 1 и присоединять к нему все перестановки из остальных элементов. Этот перебор даст (n-1)! разных туров, т.е. полный перебор в несимметричной ЗК (мы по-прежнему будем различать туры 1-3-5-4-2 и 1-2-4-5-3).
Данный алгоритм описан на языке Паскаль (см. Приложения).
Пример 2. Решим ЗК, поставленную в Примере 1 лексикографическим перебором. Приведенная выше программа напечатает города, составляющие лучший тур: 1-2-6-5-4-3 и его длину 36.
Желательно усовершенствовать перебор, применив разум. В следующем пункте описан алгоритм, который реализует простую, но широко применимую и очень полезную идею.
1.2.3. Метод ветвей и границ
К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами на основе указанного метода разработали удачный алгоритм решения ЗК и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода, но в большинстве учебников излагается пионерская работа Литтла.
Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.
Изложим алгоритм Литтла на примере 1 предыдущего раздела.. Повторно запишем матрицу:
|
- |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
- |
6 |
4 |
8 |
7 |
14 |
|
2 |
6 |
- |
7 |
11 |
7 |
10 |
|
3 |
4 |
7 |
- |
4 |
3 |
10 |
|
4 |
8 |
11 |
4 |
- |
5 |
11 |
|
5 |
7 |
7 |
3 |
5 |
- |
7 |
|
6 Рекомендуем скачать другие рефераты по теме: изложение по русскому 6 класс, деньги реферат. Предыдущая страница реферата | 2 3 4 5 6 7 8 9 10 11 12 | Следующая страница реферата Поделитесь этой записью или добавьте в закладкиКатегории: |