Как решить: Есть 7 городов, обозначенных буквами английского алфавита?
Кратчайший путь
Есть 7 городов, обозначенных буквами английского алфавита А, В, С, D, Е, F, G. Вы хотите посетить эти все города ровно по одному разу каждый и вернуться в начальную точку своего путешествия. Для этого вы можете воспользоваться самолётами: между двумя любыми городами есть прямой авиарейс. Стоимость перелёта между парой городов приведена в следующей таблице.
Необходимо построить замкнутый маршрут, проходящий через все города по одному разу, стоимость перелёта по которому была бы минимально возможной.
Расположите города в том порядке, в котором вы будете их посещать. Чем короче будет найденный вами маршрут, тем больше баллов вы получите. Обратите внимание: при расчёте стоимости маршрута также учитывается перелёт из последнего города вашего ответа в первый город.
- А
- В
- С
- D
- E
- F
- G
Ответы (5)
Про краткость маршрута замечание излишнее. Так как по условию (посещение каждого города 1 раз и построение замкнутого маршрута) предполагается построение кругового пути из 7 точек, то есть 7 перелетов. Тут ни короче ни длиннее не возможно. Длина инвариантна. Тем более в условии не различаются длины маршрутов, а различается стоимость.
Но в условии уже определено, что надо искать самый дешевый маршрут. Составители сами себя запутали.
Ну к решению.
Что можно заметить, то есть города наиболее дорогого сегмента. То есть их цены сразу начинаются с более дорогих. Потому лучше к ним добираться через более дешевые расположенные рядом с ними.
Это города B; D; F;
Вообще предпочтительней переписать таблицу для каждого города, отсортировав по возрастанию цены от него города и потом выбирать.
Например начнем с B (рядом дешевые E и C), Ну а далее будем располагать самые дешевые из доступных по возможности.
Один из вариантов
- С -(4) - B - (3) - E - (2) - D - (4) - A - (3) - G - (5) - F - (3) -
Считаем итого: получим 24
Есть ещё аналогичный вариант с другой расстановкой.
Кто меньше?
Мой ответ 24 (но не доказанный)
Здесь, наверное, имеется в виду под "короче" то, что не следует несколько раз летать в один город. То есть не следует искать самые дешёвые варианты для сокращения общей стоимости, потому что тогда будет длинный маршрут. А самый короткий вариант - это посещение каждого города по одному разу, исключение - возвращение в первый город.
Для того, чтобы подобрать самый дешёвый маршрут, я сначала выписала самые дешёвые перелёты:
G - С - 1, А - Е - 1, А - С - 2, D - Е - 2, С - F - 3, A - G - 3, В - Е - 3.
Из этих вариантов составить не получается, приходится добавлять другие, более дорогие перелёты, получается 28, а самое меньшее - 26.
Добавляю ещё: Е - F - 4, С - В - 4.
Пробую различные комбинации, чтобы как можно меньше дорогих перелётов брать, но вот два дорогих всё-таки пришлось взять, зато остальные недорогие:
F - C - G - А - Е - В - D - F
По цене: 3 + 1 + 3 + 1 + 3 + 6 + 7 = 24
Меньше у меня тоже не получилось.
Задачка о 7 городах и кратчайшем и дешевом пути имеет несколько решений (последовательностей), приводящих к минимальной цене. Важно объяснить принцип решения, а не просто подсказать готовый ответ. Подобный задачии решаются выбором наилучшего варианта:
- Из всех городов самые дорогие билеты из городов F и G, начинаем с них. Выбираем последовательности для каждого FC и GA, GC
- Дальше по стоимости идут города B и D. Для них предпочтетельнее выбрать ВЕ и DA.
- На третьем шаге, зная наиболее выгодные последовательности FCGAD (11), BE (3), соединяем их, при любом их соединении, итоговый ответ 24. Последовательност и ADBEFCG, ADEBFCG.
У меня получилось столько: ACGFEDB - 18, и если с В до А то + 5, то есть 23
ВКонтакте