Blog doktora Bota

Karkołomny Famelab


Muszę się przyznać, że moje zgłoszenie na Famelab też było nieco karkołomne:

Wierność nie popłaca

Zbytnia rozwiązłość zresztą też nie i można napisać program, który wyznaczy optymalną ilość jednoczesnych związków.

Mowa jednak nie o życiu intymnym, lecz robieniu przez internet większych zakupów i naszym związkom ze sprzedającymi nam sklepami.

Zaczęło się od tego, że Adam przy ograniczonych środkach  miał kupić spory zestaw tytułów książkowych. Jak zaczął się zastanawiać gdzie kupić to okazało się, że każdy sklep to inny wachlarz cen i to co zaoszczędzimy na jednym tytule w jednej księgarni natychmiast tracimy na innych tytułach, gdzie indziej dostępnych taniej. Postanowił więc podzielić zbiór na kilka części, ale szybko zauważył, że człowiek temu nie podoła i wpadł na pomysł programu, który by zaoferował odpowiedni dla danego zestawu i aktualnych cen w sklepach podział.

To czemu nie kupić każdej książki w innym, najtańszym dla niej sklepie? Propozycja upada z powodu kosztów dostawy, które są naliczane już w przypadku zakupu w danym sklepie jednej książki i nie rosną z liczbą książek kupowanych jednocześnie w tym sklepie. To skutecznie ogranicza podziały zestawu na zbyt wiele sklepów. Bowiem wtedy na pewno koszty zakupu są większe niż przy bardziej pogrupowanych zakupach.

Okazuje się jednak, że prawdopodobnie nie istnieje algorytm, który by sprawnie wyszukał optymalny podział zestawu towarów.

Mówię w trybie przypuszczającym, gdyż udało się udowodnić przynależność tego problemu dla klasy silnie NP.-zupełnych. O tej klasie jednak nie potrafimy zdecydować czy na pewno nie można ich sprawnie rozwiązać. Jednak przez kilkadziesiąt lat badania złożoności obliczeniowej problemów dla żadnego problemu z tej klasy nie znaleziono szybkiej metody. Jest to o tyle wymowne, że wystarczyłoby to zrobić dla jednego problemu by wykazać, że możliwe jest dla wszystkich pozostałych. W każdym razie na razie musimy traktować problemy z tej klasy jako nie dające się szybko rozwiązać.

Co więc zrobić? Trzeba więc budować szybsze ale mniej doskonałe algorytmy. Dzięki temu co prawda nie wyciśniemy ze sklepów ostatniej złotówki, ale znajdziemy rozwiązanie, które zaoszczędzi nam złotówek i to zanim … odechce nam się zakupów, albo co gorsza umrzemy. Bo takie niepewne algorytmy potrafią liczyć naprawdę bardzo długo i trudno to do końca przewidzieć.

Udało się nam jednak podać co najmniej kilka algorytmów, które sprawnie liczą. Wtedy porównywarka przypomina bardziej sklep internetowy, w którym do koszyka wkładamy poszczególne artykuły, których ceny dokładnie nie znamy, bo w różnych sklepach jest różna ale jest to ten sam artykuł. Dopiero przycisk „Optymalizuj zakupy” odsłania ceny i miejsca skąd wybrano artykuły oraz wyznacza cenę w założeniu bardzo zbliżoną do optymalnej. Dzisiejsze zasady współpracy porównywarek ze sklepami zmuszają do samodzielnego odwiedzenia każdego ze sklepów i dokonania zamówienia dokładnie według planu optymalizacji zakupów. Jednak w przyszłości porównywarka będzie sama zamawiała towary i rozdzielała wyasygnowaną przez nas kwotę na odpowiednie sklepy. W ten sposób działanie takiej porównywarki zauważymy dopiero przy odbiorze pakunków, które zbiegną w różnym czasie i od różnych dostawców. Pewnie nawet nie zauważymy o ile taniej kupimy, że naszą niewierność jednemu sklepowi zapewni porównywarka cen w swoim najnowocześniejszym wcieleniu nieobecnym jeszcze w naszym internecie.

Share this Story
Zobacz inne podobne wpisy
  • Elektryfikacja bezprzewodowa

    Elektryfikacja przewodowa rozpoczęła się ponad sto lat temu, natomiast elektryfikację bezprzewodową dużej mocy rozpoczęliśmy zaledwie dekadę temu. Opanowanie elektryczności, na dobre zapoczątkowane ...
  • Karty perforowane miłością

    Czy tchnące kurzem karty perforowane używane w dawno już przestarzałych komputerach mogą być romantyczne? Przeszklone drzwi kryją za sobą surowe pomieszczenie ...
  • Środowiska programowania dla dzieci

    Jeszcze w latach osiemdziesiątych nauką programowania w językach proceduralnych typu FORTRAN, ALGOL 60 czy PASCAL objęci byli wszyscy studenci politechniki. W ...
  • Naręczny tablet z ręcznym ekranem

    Osiem miesięcy temu… Pisałem jaką radość sprawił mi naręczny smartfon: Komórka na rękę Po tym czasie ośmiu miesięcy… muszę przyznać, że ...
  • Praca doktorska – jak ją napisać błyskotliwie ?

    By powstała  praca doktorska nie wystarczy pokazać, że się coś umie lecz wykazać się dokonaniem czegoś nowego, co ma wartość poznawczą. ...
  • Naukowa Gwiazdka w Domu Dziecka

    Wiedza naukowa z trudem przenika przez mury zwykłych mieszkań, a pewnie nie łatwiej jej trafić do domów dziecka. Pomysł jest taki, żeby zaprosić ...
  • Co szybsze? – Mózg czy komputer?

    Nie ma jednoznacznej odpowiedzi na pytanie czy szybsze są komputery czy ludzkie mózgi. Wszystko zależy od tego jakie zadania im stawiamy. ...
  • Księżycowa gospodarka

    Zdaje się, że wreszcie po 45 latach księżycowa perspektywa podboju kosmosu powraca. Zrozumiano, że to nie tylko przystanek w locie na ...
  • Prapoczątki gospodarki elektronicznej

    Za początki gospodarki elektronicznej uważa się rok 1995. Ale czy na pewno przedtem nie było niczego? Jak zaczniemy się cofać to trafimy ...
  • Gimnazjalistka – historyk

    Rozmawiam dzisiaj z Patrycją Wasielewską – gimnazjalistką, której przewodnik po Poznańskim Czerwcu ‘56 zdobył pierwszą nagrodę w konkursie organizowanym przez Instytut ...
  • Zrobili artyści czy inżynierowie?

    Formalnie rzecz biorąc to Marcin i Tomek – przyszli inżynierowie zauważyli i docenili temat dyplomu jaki „wisiał” u mnie od kilku lat. ...
  • Pałac matematyki

    Bez matematyki nie byłoby większości współczesnych nauk. Nawet wiekopomne dzieło Kopernika oparte jest na rozważaniach matematycznych. A jednak ta królowa nauk ...
Zobacz inne wpisy Andrzej P. Urbański
  • Elektryfikacja bezprzewodowa

    Elektryfikacja przewodowa rozpoczęła się ponad sto lat temu, natomiast elektryfikację bezprzewodową dużej mocy rozpoczęliśmy zaledwie dekadę temu. Opanowanie elektryczności, na dobre zapoczątkowane ...
  • Karty perforowane miłością

    Czy tchnące kurzem karty perforowane używane w dawno już przestarzałych komputerach mogą być romantyczne? Przeszklone drzwi kryją za sobą surowe pomieszczenie ...
  • Środowiska programowania dla dzieci

    Jeszcze w latach osiemdziesiątych nauką programowania w językach proceduralnych typu FORTRAN, ALGOL 60 czy PASCAL objęci byli wszyscy studenci politechniki. W ...
  • Naręczny tablet z ręcznym ekranem

    Osiem miesięcy temu… Pisałem jaką radość sprawił mi naręczny smartfon: Komórka na rękę Po tym czasie ośmiu miesięcy… muszę przyznać, że ...
  • Praca doktorska – jak ją napisać błyskotliwie ?

    By powstała  praca doktorska nie wystarczy pokazać, że się coś umie lecz wykazać się dokonaniem czegoś nowego, co ma wartość poznawczą. ...
  • Naukowa Gwiazdka w Domu Dziecka

    Wiedza naukowa z trudem przenika przez mury zwykłych mieszkań, a pewnie nie łatwiej jej trafić do domów dziecka. Pomysł jest taki, żeby zaprosić ...
  • Co szybsze? – Mózg czy komputer?

    Nie ma jednoznacznej odpowiedzi na pytanie czy szybsze są komputery czy ludzkie mózgi. Wszystko zależy od tego jakie zadania im stawiamy. ...
  • Księżycowa gospodarka

    Zdaje się, że wreszcie po 45 latach księżycowa perspektywa podboju kosmosu powraca. Zrozumiano, że to nie tylko przystanek w locie na ...
  • Prapoczątki gospodarki elektronicznej

    Za początki gospodarki elektronicznej uważa się rok 1995. Ale czy na pewno przedtem nie było niczego? Jak zaczniemy się cofać to trafimy ...
  • Zrobili artyści czy inżynierowie?

    Formalnie rzecz biorąc to Marcin i Tomek – przyszli inżynierowie zauważyli i docenili temat dyplomu jaki „wisiał” u mnie od kilku lat. ...
  • Pałac matematyki

    Bez matematyki nie byłoby większości współczesnych nauk. Nawet wiekopomne dzieło Kopernika oparte jest na rozważaniach matematycznych. A jednak ta królowa nauk ...
  • Chiny liczą na potęgę

    Zaprezentowana w roku 1963, maszyna nazwana CDC 6600 w powszechnym mniemaniu uważana jest za pierwszy superkomputer świata, czyli reprezentanta klasy komputerów, ...
Zobacz inne w kategorii Blog doktora Bota

Zobacz

Elektryfikacja bezprzewodowa

Elektryfikacja przewodowa rozpoczęła się ponad sto lat temu, natomiast ...

Inline
Inline