Представление решений

Для подобных задач необходимо определиться со способом представления потенциальных решений. Функции оптимизации, с которыми вы вскоре ознакомитесь, достаточно общие и применимы к различным задачам, поэтому так важно выбрать простое представление, которое не было бы привязано к конкретной задаче о групповом путешествии. Очень часто для этой цели выбирают список чисел. Каждое число обозначает рейс, которым решил лететь участник группы, причем 0 – это первый рейс в течение суток, 1 – второй и т. д. Так как каждый человек должен лететь туда и обратно, то длина списка в два раза больше количества людей.

Например, в решении, представленном списком

[1,4,3,2,7,3,6,3,2,4,5,3] Сеймур (Seymour) летит вторым рейсом из Бостона в Нью-Йорк и пятым рейсом из Нью-Йорка в Бостон, а Фрэнни (Franny) – четвертым рейсом из Далласа в Нью-Йорк и третьим рейсом обратно.

Поскольку интерпретировать решение, имея перед собой лишь список чисел, трудно, нам понадобится функция, которая печатает выбранные рейсы в виде красиво отформатированной таблицы. Добавьте ее в файл optimization.py:

def printschedule(r): for d in range(len(r)/2): name=people[d][0] origin=people[d][1]

out=flights[(origin,destination)][r[d]]

ret=flights[(destination,origin)][r[d+1]]

print ‘%10s%10s %5s-%5s S%3s %5s-%5s S%3s’ %% (name,origin,

out[0],out[1],out[2], ret[0],ret[1],ret[2])

В каждой строке эта функция печатает имя человека, аэропорт назначения, время вылета, время прилета и цены на билеты туда и обратно. Протестируйте ее в интерактивном сеансе: >>> import optimization >>> s=[1,4,3,2,7,3,6,3,2,4,5,3] >>> optimization.printschedule(s)

Seymour

Boston

12

1:34-15:02

$10Q

12:08-14:05

$142

Franny

Dallas

12

l:1Q-15:25

$342

Q:4Q-13:51

$22Q

Zooey

Akron

Q’

15-12:14

$247

15:50-18:45

$243

Walt

Miami

15

.:34-18:11

$326

14:08-16:0Q

$232

Buddy

Chicago

14

1:22-16:32

$126

15:04-17:23

$18Q

Les

Omaha

15

.:03-16:42

$135

6:1Q- 8:13

$23Q

Даже если не обращать внимания на цены, в таком расписании есть ряд неувязок. В частности, раз все члены семьи хотят уехать из аэропорта и приехать в него вместе, то все они должны прибыть к 6 часам утра, когда отправляется рейс Леса (Les), хотя некоторые смогут улететь только в 4 часа дня. Чтобы найти оптимальное решение, программа должна взвесить свойства различных расписаний и решить, какое из них наилучшее.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100