Calc - Задача коммивояжера (потратить минимум денег на посещение нескольких городов)

Модератор: /dev/random

Stasroot1
Сообщения: 1026
ОС: Debian9

Calc - Задача коммивояжера (потратить минимум денег на посещение нескольких городов)

Сообщение Stasroot1 »

Здравствуйте. Как в LibreOffice 4.3.3.2 решить задачу коммивояжера? Есть табличка со стоимостью перелетов из каждого города в каждый город. Городов 4. При этом стоимость перелета например из города 1 в город 2 составляет 100, а в обратном направлении например 140.
Вопрос: как найти самый дешевый по стоимости перелетов маршрут? При этом: Каждый город можно посетить только один раз.

Никогда задачи такого рода ни в каком офисном пакете не решал. а тут потребовалось. Подскажите как это сделать?
Спасибо сказали:

Аватара пользователя
SLEDopit
Модератор
Сообщения: 4762
Статус: фанат консоли (=
ОС: GNU/Debian, RHEL

Re: Calc - Задача коммивояжера (потратить минимум денег на посещение нескольких городов)

Сообщение SLEDopit »

Гуглить не пробовали?
Вот, например, или вот. Оно хоть и делалось для excel'я, если не заведётся, хотя бы логику можно подсмотреть.
UNIX is basically a simple operating system, but you have to be a genius to understand the simplicity. © Dennis Ritchie
The more you believe you don't do mistakes, the more bugs are in your code.
Спасибо сказали:

Stasroot1
Сообщения: 1026
ОС: Debian9

Re: Calc - Задача коммивояжера (потратить минимум денег на посещение нескольких городов)

Сообщение Stasroot1 »

Да смотрел. только там, по первой ссылке рассматривается вариант с расчетеом расстояний по координатам. и в той задаче получается расстояние из города А в город Б равно в двух направлениях друг другу. У меня стоимость и она к моему удивлению совсем не одинаковая в разных направлениях. Т.е. из Москвы в Питер стоит 100 а из Питера в Москву стоит 132. Плюс по аналогии.. я задачами ни в экселеле ни в кальке не занимался.
Вторая ссылка на английском. Почитал. Там теоретические раскладки и вариации. Намного более полная инфа по сравнению с той что я находил на русском языке.

Будем разбираться...
Спасибо сказали:

NickLion
Сообщения: 3408
Статус: аватар-невидимка
ОС: openSUSE Tumbleweed x86_64

Re: Calc - Задача коммивояжера (потратить минимум денег на посещение нескольких городов)

Сообщение NickLion »

Ну, так сделайте несимметричную таблицу и разверните её в полный список дуг.
Спасибо сказали:

Stasroot1
Сообщения: 1026
ОС: Debian9

Re: Calc - Задача коммивояжера (потратить минимум денег на посещение нескольких городов)

Сообщение Stasroot1 »

NickLion писал(а):
18.04.2016 12:03
несимметричную таблицу и разверните её в полный список дуг.

Это как? :wacko:
Спасибо сказали:

NickLion
Сообщения: 3408
Статус: аватар-невидимка
ОС: openSUSE Tumbleweed x86_64

Re: Calc - Задача коммивояжера (потратить минимум денег на посещение нескольких городов)

Сообщение NickLion »

Stasroot1
Ну, как в примере №1, таблица расстояний, только заполнить таблицу нужными значенями. Т.к. путь из 1 в 2 ≠ 2 в 1, то таблица не будет симметричной. Далее, разворачиваете в таблицу дуг (в примере, 2-й скриншот), только там будут и 1 2, так и 2 1. Ну, и ограничения правильные задать.
Спасибо сказали: