Algorytm zachłanny czy programowanie dynamiczne?

0

Witam, mam napisac poniższy algorytm:

Biuro podróży chce wprowadzić pewne optymalizacje w kosztach podróży.
Podróżni w drodze spędzają czasem wiele dni zatem opłaty za noclegi stanowią poważną część
kosztów podróży. Ze względu na bezpieczeństwo podróży każdy autokar jedzie w ciągu dnia i nie
może przejechać więcej niż 800 kilometrów. Noc na trasie poza końcem i początkiem podróżni i
kierowcy spędzają w hotelach. Podróż trzeba zaplanować optymalnie, żeby liczba noclegów w
ciągu całej wycieczki była jak najmniejsza. Biuro podróży znając potrzebę obniżenia kosztów
wycieczki, postanowiło zbadać czy opłaci się układanie planów podróży tak , aby suma opłat za
noclegi była możliwie najniższa, nawet wtedy gdyby to miało przedłużyć podróż. W każðej ofercie
podana jest odległość hotelu od początku trasy i cena jednostkowa za hotel. Podróżni podróżują
tylko w jedną stronę. Trasa nie ma rozgałęzień. Przez każdy punkt trasy autokar przejeżdża tylko
raz. Nie ma dwóch hoteli w jednym punkcie,wiec każdy hotel może być zidentyfikowany przez
jego odległość od początku trasy. Nie planuje się noclegu ani na początku ani na końcu trasy.
Liczba osób w autobusie nie zmienia się i wszyscy razem z kierowcą płacą taką samą cenę
jednostkową za nocleg w tym samym hotelu. Pojemność hotelu jest tak duża, że wszyscy razem
mogą zanocować w jednym hotelu. Na każdym odcinku trasy o długości 800km jest przynajmniej
jeden hotel, w który można zanocować. Zakładamy, że długość trasy jest liczbą całkowitą
d<=16000, a liczba hoteli h<=1000.
Napisz algorytm, który po wczytaniu długości trasy, liczby hoteli oraz ceny za nocleg w każdy z
hoteli za jedną osobę znajdzie najtańszy plan podróży, tzn. taki, której suma opłat za hotele była jak
najmniejsza, a jeśli takich rozwiązań jest wiele, wybiera jedno rozwiązanie z najmniejszą liczbą
noclegów.
Przykład
Dane:
d=2000
Liczba hoteli h=7
Oferty hoteli posortowane według rosnącej odległości od początku trasy (odległość od początku
trasy i cena za nocleg):
100 54, 120 70, 400 17, 700 38, 1000 25, 1200 18, 1440 40
Wynik:
odległość kolejnych noclegów od początku trasy: 400, 1200
koszt: 35

Stąd moje pytania:
1.Zda się tu algorytm zachłanny? (jeśli tak, to jakie ma mieć kryterium wyboru?)
2. Programowanie dynamiczne? (Na jakie podproblemy to rozbić? Da ktoś wskazówki na zależności rekurencyjne)?

Proszę o jakieś nakierowanie

1

Do czego Ci to?

Nie wiem co tu robic zachłannie, zrób dynamika.

Zauważ dwie rzeczy:

  1. Potraktuj początek i koniec jak hotel za darmo (dołóż je).
  2. Dla każdego hotelu wystarczy że popatrzysz na te 800km przed nim - taki zasieg ma Автобус.
0

Czyli jak mają wyglądać zależności?

s(n,d)- najmniejszy koszt za noclegi, mając od dyspozycji n hoteli oraz drogę o długości d do przejechania.

-jeśli d=0 lub n=0 to wstawiamy w tabelkę nieskończoność. (dużą liczbę) czyli np. s(0,0)=100000
-jeśli odległość hotelu jest większa niż wielkość trasy to nie bierzemy hotelu(ilość hoteli się zmniejsza, dystans się nie zmienia), czyli s(n,d)=s(n-1,d)
-w przeciwnym wypadku bierzemy opcję która mniej kosztuje (albo bierzemy hotel, wtedy do wyniku dodajemy jego cenę, albo nie bierzemy)
czyli s(n,d)=MIN(s(n-1,d),s(n-1,d-odległość i-tego hotelu)+cena itego hotelu).

co o tym sądzicie? dla mnie wydaje się że jest coś do poprawy, ale nie mogę wykminić.

1

Trudno się to czyta, tzn. ja bym Ci radził o ile zrozumienie formalne, zapis jest ważne to jednak skup się na istocie problemu. To znaczy, robiłem kiedyś podobnie jak startowałem w OMie gdzie często miałem opanowaną całą teorie do maszynki i próbowałem ją zastosować. Myśląc w tym paradgmacie programowania dynamicznego, chcesz wykorzystać jakieś informację. Zacznij od bruteforce, umiesz w ogóle rozwiązać to zadanie? Później zobacz co mozna zrobić lepiej. Tutaj, zauważ że chcemy przebyć całą tą drogę od lewej do prawej, odwiedzając tylko niektóre hotele. No własnie. Zauważ że to ograniczenie na drogę mówi nam tylko ile kroków możemy zrobić. Kolejna obserwacja, punkty pośrednie nie mają znaczenia, jeśli dołożymy sobie startowy hotel i końcowy możemy się skupić tylko na hotelach, racja? Wiemy również z treści, że rozwiązanie zawsze istnieje.

Co teraz?

Zastanówmy się dla każdego hotelu, w porządku który dostajemy, jak najtaniej się do niego dostać. Tyle i aż tyle. Patrząc na kolejny z kolei hotel (dalszy od początku) i mając odpowiedź dla poprzednich hoteli możemy odpowiedzieć sobie na pytanie jak najtaniej możemy do tego hotelu się dostać. Zgadza się? Jak to zrobić? Pomyśl jak to rozwiązać, musisz rozumieć tylko idee programowania dynamiczniego, jeśli to złapiesz, to sobie formalizuj. Formalizacja jest dobra jeśli rozumiesz sedno, to jest jednak moja rada. Być może znajdziesz ludzi którzy powiedzą że zła, ale tak Ci radzę. Jak to masz, to spróbuj to sformalizować tak jak to robisz właśne, nastepnie przelej to na kod (to juz mozna zrobic wrecz wprost) :) Powodzenia

0

A co sądzisz aby zrobić to za pomocą takiego grafu skierowanego ważonego że:
-wierzchołkami są kolejne dystanse na którym znajduje się hotel.
-krawędź łączy wierzchołki, jeśli ich różnica wartości jest mniejsza, równa 800.
-waga krawędzi jest równa cenie hotelu, do którego grot strzałki jest skierowany.

graf wygląda mniej więcej tak:
title

Dalej za pomocą algorytmu Dijkstry znajduję ściężkę od początku do końca o najmniejszej wadze.

1

Przeczytaj mój post zdanie po zdaniu. Tam gdzie jest pytanie, odpowiedz na nie.

To co napisałeś, spoko, rozumiem że to Twój bruteforce? Jaka jest złożoność stworzenia takiego grafu? Znajdź taki przykład który spowoduję że będzie to wolne. Jeśli masz juz graf, to prawda będzie to szybko. Niestety, w zadaniu nie ma mowy o grafie.

1
Czarny Pomidor napisał(a):

Przeczytaj mój post zdanie po zdaniu. Tam gdzie jest pytanie, odpowiedz na nie.

To co napisałeś, spoko, rozumiem że to Twój bruteforce? Jaka jest złożoność stworzenia takiego grafu? Znajdź taki przykład który spowoduję że będzie to wolne. Jeśli masz juz graf, to prawda będzie to szybko. Niestety, w zadaniu nie ma mowy o grafie.

Popatrzyłem jeszcze raz, źle napisałem.:D

Jest w porządku, możesz tak zrobić. To się trochę sprowadza do tego co napisałem, tyle że tutaj więcej trzeba zakodzić. Także, spoko. Jaka będzie złożoność Twojego rozwiązania?

0

dzięki, wpadłem na to dzięki temu zdaniu "Zastanówmy się dla każdego hotelu, w porządku który dostajemy, jak najtaniej się do niego dostać". Implementowałem wcześniej algorytm Dijsktry i wiem, że ten algorytm szuka najkrótszych ścieżek ze źródła do pozostałych wierzchołków. A tu źródłem jest "Początek" i trzeba znaleźć minimalną ścieżkę do "Koniec".
Co do złożoności, to chyba będzie to O(n^2) gdyż przy tworzeniu macierzy incydencji, będzie trzeba porównywać każdy hotel z każdym(naiwny?). Chyba że posortować hotele przez zliczanie względem dystansu(O(n))(16000 to duży przedział?) i wtedy będzie można breakować, gdy już w porównywaniu znajdzie się dystans między hotelami większy niż 800, co na pewno mniejszy złożoność

1
spamgolden napisał(a):

dzięki, wpadłem na to dzięki temu zdaniu "Zastanówmy się dla każdego hotelu, w porządku który dostajemy, jak najtaniej się do niego dostać". Implementowałem wcześniej algorytm Dijsktry i wiem, że ten algorytm szuka najkrótszych ścieżek ze źródła do pozostałych wierzchołków. A tu źródłem jest "Początek" i trzeba znaleźć minimalną ścieżkę do "Koniec".
Co do złożoności, to chyba będzie to O(n^2) gdyż przy tworzeniu macierzy incydencji, będzie trzeba porównywać każdy hotel z każdym(naiwny?). Chyba że posortować hotele przez zliczanie względem dystansu(O(n))(16000 to duży przedział?) i wtedy będzie można breakować, gdy już w porównywaniu znajdzie się dystans między hotelami większy niż 800, co na pewno mniejszy złożoność

Ok, warto to zrobić jeszcze bez tego drzewka, skoro się już uczysz dynamicznego programowania. Złożoność jest taka sama, ale kodu mniej.

0

a więc dla podanych w przykładzie wartości

  • dla hotelu nr1.(100). mamy tylko jedną możliwość dostania się. trzeba zapłacić 54.
    -dla hotelu nr2.(120). najtaniej będzie jak bez postoju do niego dojedziemy i zapłacimy 70.
    -dla hotelu nr3(400), najtaniej będzie jak bez postaju dojedziemy. zapłacimy 17.
  • dla hotelu nr4(700), najtaniej będzie jak bezpośrednio dojedziemy z początku. zapłacimy 38.
    -dla hotelu nr5(1000). bierzemy pod uwagę tylko poprzednie hotele ktore są w odległości nie większej niż 800, i bierzemy minimum. więc najlepiej będzie jak zatrzymamy się w hotelu nr3 i dojedziemy do nr5. cena to 17+25=42.
    -dla hotelu nr6(1200), analogicznie. warunek spełniają hotele nr3, nr4, nr5. najoptymalniej bierzemy hotel nr3. więc 17+18=35.
    -dla hotelu nr7(1440), warunek spełniają hotele nr4, nr5, nr6. bierzemy minimum, czyli 35+40=75.
    -dla końca- wrunek spełniają hotele nr6 i nr7. bierzmy minimum, czyli 35+0=35.

co o tym sądzisz?

1
spamgolden napisał(a):

a więc dla podanych w przykładzie wartości

  • dla hotelu nr1.(100). mamy tylko jedną możliwość dostania się. trzeba zapłacić 54.
    -dla hotelu nr2.(120). najtaniej będzie jak bez postoju do niego dojedziemy i zapłacimy 70.
    -dla hotelu nr3(400), najtaniej będzie jak bez postaju dojedziemy. zapłacimy 17.
  • dla hotelu nr4(700), najtaniej będzie jak bezpośrednio dojedziemy z początku. zapłacimy 38.
    -dla hotelu nr5(1000). bierzemy pod uwagę tylko poprzednie hotele ktore są w odległości nie większej niż 800, i bierzemy minimum. więc najlepiej będzie jak zatrzymamy się w hotelu nr3 i dojedziemy do nr5. cena to 17+25=42.
    -dla hotelu nr6(1200), analogicznie. warunek spełniają hotele nr3, nr4, nr5. najoptymalniej bierzemy hotel nr3. więc 17+18=35.
    -dla hotelu nr7(1440), warunek spełniają hotele nr4, nr5, nr6. bierzemy minimum, czyli 35+40=75.
    -dla końca- wrunek spełniają hotele nr6 i nr7. bierzmy minimum, czyli 35+0=35.

co o tym sądzisz?
Jest w porządku.

Dla każdego hotelu będzemy trzymac tablice, która powie nam jaki jest minimalny koszt dotarcia do tego hotelu przy ograniczeniach w zadaniu. Algorytm: Dla każdego hotelu w kolejności rosnącej odległości od początku przeglądamy poprzednie hotele które są w promieniu d. Bierzemy minimum z tych hoteli i dodajemy do kosztu aktualnie przetwarzanego hotelu.

1
Czarny Pomidor napisał(a):
spamgolden napisał(a):

a więc dla podanych w przykładzie wartości

  • dla hotelu nr1.(100). mamy tylko jedną możliwość dostania się. trzeba zapłacić 54.
    -dla hotelu nr2.(120). najtaniej będzie jak bez postoju do niego dojedziemy i zapłacimy 70.
    -dla hotelu nr3(400), najtaniej będzie jak bez postaju dojedziemy. zapłacimy 17.
  • dla hotelu nr4(700), najtaniej będzie jak bezpośrednio dojedziemy z początku. zapłacimy 38.
    -dla hotelu nr5(1000). bierzemy pod uwagę tylko poprzednie hotele ktore są w odległości nie większej niż 800, i bierzemy minimum. więc najlepiej będzie jak zatrzymamy się w hotelu nr3 i dojedziemy do nr5. cena to 17+25=42.
    -dla hotelu nr6(1200), analogicznie. warunek spełniają hotele nr3, nr4, nr5. najoptymalniej bierzemy hotel nr3. więc 17+18=35.
    -dla hotelu nr7(1440), warunek spełniają hotele nr4, nr5, nr6. bierzemy minimum, czyli 35+40=75.
    -dla końca- wrunek spełniają hotele nr6 i nr7. bierzmy minimum, czyli 35+0=35.

co o tym sądzisz?

Jest w porządku.*

Dla każdego hotelu będzemy trzymac tablice, która powie nam jaki jest minimalny koszt dotarcia do tego hotelu przy ograniczeniach w zadaniu. Algorytm: Dla każdego hotelu w kolejności rosnącej odległości od początku przeglądamy poprzednie hotele które są w promieniu d. Bierzemy minimum z tych hoteli i dodajemy do kosztu aktualnie przetwarzanego hotelu.

0

title

Czyli formalnie to będzie zależność rekurencyjna:
Z(n)=MIN(Z(n-1)+Cn,Z(n-2)+Cn,...,Z(n-k)+Cn)
dla Dn<=Dk+800

gdzie Z(n)- najtańsza droga z noclegami do hotelu o numerze n.
Cn- cena noclegu n tego hotelu.
Dn-odległość n-tego hotelu.

1
spamgolden napisał(a):

title

Czyli formalnie to będzie zależność rekurencyjna:
Z(n)=MIN(Z(n-1)+Cn,Z(n-2)+Cn,...,Z(n-k)+Cn)
dla Dn<=Dk+800

gdzie Z(n)- najtańsza droga z noclegami do hotelu o numerze n.
Cn- cena noclegu n tego hotelu.
Dn-odległość n-tego hotelu.

Tak, załapałeś. Rzecz ekstra to nie potrzebujesz dodatkowej pamięci, możesz wykorzystać tablicę którą masz na wejściu:)

1 użytkowników online, w tym zalogowanych: 0, gości: 1