Xpoint
   [напомнить пароль]

Максимальное соответствие чисел

Метки: [без меток]
2005-04-25 19:08:05 [обр] strlen[досье]

Имеются две последовательности. Одна состоит только из натуральных чисел, другая из последовательности последовательностей натуральных чисел. Назовем первую "очередь покупателей", а вторую "очередь продавцов":

"очередь покупателей": 1, 1, 1, 1, 1, 1, 4, 1, 1, 7, 1, 2, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 5, 2, 1, 1, 2
"очередь продавцов": [10], [2..6], [5..10], [11], [8], [12..17], [4], [1], [2] ,[1]

[2..6] означает последовательность от 2 до 6 (2,3,4,5,6)

Задача: продать максимальное количество товаров максимальному количеству покупателей в порядке очереди.

Ограничения: один покупатель покупает только у одного продавца.
Чем раньше покупатель находиться в очереди, тем выгоднее покупка, так как продавцы расположены в порядке возростания цены.
Продавец [2..6] согласен продать не менее двух единиц товара, и не более шести. Продавец [10] согласен продать не менее и не более десяти единиц.

Одно из решений приведенного примера задачи:

1, 1, 1, 1, 1, 1, 4->[10]
1, 1->[2..6]
7->[5..10]
1, 2->[2..6]
3->[5..10]
1->[2..6]
2, 1, 1, 1, 1, 1, 1, 1, 1->[11]
5, 2, 1->[8]
1->[11]
1->[1]
2->[2]

В данный момент я набросал "жадный" алгоритм, но он, разумеется, не заботиться о благосостоянии покупателей и продавцов, то есть часто дает результат далекий от оптимального.

Буду рад любым идеям.

спустя 12 часов [обр] VIG(38/839)[досье]
сообщение промодерировано

Задачка несколько смутная ...

Что значит "Чем раньше покупатель находится в очереди, тем выгоднее покупка, так как продавцы расположены в порядке возрастания цены"? Как это влияет на оптимальность решения? И какой в точности критерий оптимальности? Что значит "алгоритм ... не заботится о благосостоянии покупателей и продавцов", так сказать, математически выражаясь?

Интересно также, откуда эта задачка взялась, т.е. какой она имеет прикладной смысл ...

спустя 6 часов [обр] strlen[досье]

Спасибо за вопросы.

Задачка несколько смутная...

 Полностью согласен, иногда, сложность задачи определяеться не ее настоящей сложностью, а именно сложностью определения, но надо же было с чего-то начитать. Я посторяюсь ответить на ваши вопросы и тогда, возможно, что-нибудь проясниться.
Отвечу сразу на последний вопрос. Сама задача взята из реального проекта. Прикладной смысл задача имеет в различных областях, касающихся разумному распределению ресурсов. Примеров можно приводить, множество: начиная с оптимального распределения задач рабоникам фирмы до распределения денежных средств из гос. бюджета.

На самом деле, мне кажеться, что задача уже давно решена. Просто, из-за завуалированности этой задачи, я не могу это решение откопать.
Судя по количеству возможных решений думаю тут пахнет AI.

Что значит "Чем раньше покупатель находится в очереди, тем выгоднее покупка, так как продавцы расположены в порядке возрастания цены"?

Все очень просто: каждый покупатель имеет свой приоритет (1,2,3,4..), короче, FIFO (скажем, чем число меньше, тем приоритет выше), каждый продавец тоже имеет свой приоритет (по такому же принципу). Если покупатель с приоритетом 1 покупает у продавца с приоритетом 1, а покупатель с приоритетом 2 покупает у продавца с приоритетом 2, то это решенее оптимальнее чем если бы покупатель с приоритетом 1 покупает у продавца с приоритетом 2, а покупатель с приоритетом 2 покупает у продавца с приоритетом 1.

Как это влияет на оптимальность решения? И какой в точности критерий оптимальности? Что значит "алгоритм ... не заботится о благосостоянии покупателей и продавцов", так сказать, математически выражаясь?

Я думаю, стоит разделить задачу на две части, точнее определить две цели:

  1. Расспределение товаров всем покупателям (о продавцах, действительно, заботиться не надо, они сами о себе позаботяться:)
  2. Расспределение товаров в порядке очереди (тот кто первый стоит в очереди, тот имеет приоритет получить товар по более низкой цене, хотя гарантий таких ему никто не давал именно из-за пункта 1)

Выражаясь терминами искуственного интелекта эвристика такова:
h1(n) - количество товара неполученного покупателями
h2(n) - функция подчсета суммы неточности распределения в порядеке очереди. Идеальный вариант 0, когда каждый получает товар в свою очередь. А если, например, в итоге покупатели получили товар в следуеещем порядке: 3,2,4,1,5, то h2(n)=2+0+1+3+0=6

h(n)=h1(n)+h2(n)
чем меньше h(n), тем лучше (это и есть точность оптимальности)

Надеюсь, проблема стала более ясна.

Можно упростить проблему и убрать пункт 2, тогда остаеться лишь проблема расспределения.
Если проблема расспределения вам кажется более простой и ясной, то буду рад любым идеям.

спустя 10 часов [обр] VIG(38/839)[досье]

Увы, ничем не могу Вас порадовать: "искусственного интеллекта", чтО бы под этим термином ни понимать, для решения задачи в данной постановке недостаточно ...

Рассмотрим случай всего двух продавцов [N] [N]. И некоторого числа покупателей с общей потребностью 2N. Распродать товар (в этом случае — или все или ничего) удастся тогда и только тогда, когда существует подмножество множества покупателей с суммарной потребностью N. А нахождение такого "половинного" подмножества — суть известная NP-полная задача ...

Посему имеются следующие возможности:

  1. Плюнуть: "ну не шмогла" (с).
  1. Попробовать переформулировать задачу, чтобы с прикладной точки зрения особой разницы не было (оптимизация — это в большинстве случаев штука весьма условная, зависящая от модели), а с математической — чтобы избавиться от NP.
  1. Погрязнуть в эвристиках и частных алгоритмах, которые вроде бы замечательно работают на тестовых и модельных примерах, но всегда разваливаются на сколько-нибудь интересных задачах (тем они, эти задачи, и интересны, однако).
  1. Последовать примеру Кристобаля Хозевича Хунты и провозгласить: "Мы сами знаем, что она [задача] не имеет решения. Мы хотим знать, как ее решать." Вот взять, навалиться, да и порешать проблему NP-полноты, слабо? В случае успеха, помимо всемирной славы, — вполне конкретный зеленый мульён от Института Клэя, для начала ... :-)

 

спустя 53 минуты [обр] strlen[досье]

Спасибо за анализ проблемы.
Я на что-то меньшее чем NP и не расчитывал:), поэтому другого подхода как через эвристику не видел.
Радует, хотя бы то, что мне удалось объяснить суть задачи.
Пункты 1, 4 буду "иметь в виду", насчет пункта 2 - как ни крути, а нахождение такого "половинного" подмножества — суть известная NP-полная задача ...
Я попытался перефразировать проблему, но вышло тоже самое (может чуть яснее)
http://forum.vingrad.ru/index.php?showtopic=49953
а изменить саму суть задачи никак нельзя

Остаеться погрязнуть в эвристиках и частных алгоритмах :)

Powered by POEM™ Engine Copyright © 2002-2005