Qualcuno può aiutare a risolvere questo complesso problema algoritmico?

(Aggiornamento: ora consente una dimensione massima del serbatoio del gas)

Puoi risolverlo in tempo lineare come segue:

void FindStartingPoint(int[] gasOnStation, int[] gasDrivingCosts, int gasTankSize)
{
  // Assume gasOnStation.length == gasDrivingCosts.length
  int n = gasOnStation.length;

  // Make a round, without actually caring how much gas we have.
  int minI = 0;
  int minEndValue = 0;
  int gasValue = 0;
  for (int i = 0; i < n; i++)
  {
    if (gasValue < minEndValue)
    {
      minI = i;
      minEndValue = gasValue;
    }
    gasValue = gasValue + gasOnStation[i] - gasDrivingCosts[i];
  }

  if (gasValue < 0)
  {
    Console.WriteLine("Instance does not have a solution: not enough fuel to make a round.");
  }
  else
  {
    // Try a round.
    int gas = DoLeg(0, minI, gasTankSize);
    if (gas < 0)
    {
      Console.WriteLine("Instance does not have a solution: our tank size is holding us back.");
      return;
    }
    for (int i = (minI + 1) % n; i != minI; i = (i + 1) % n)
    {
      gas = DoLeg(gas, i, gasTankSize);

      if (gas < 0)
      {
        Console.WriteLine("Instance does not have a solution: our tank size is holding us back.");
        return;
      }
    }
    Console.WriteLine("Start at station: " + minI);
  }
}
int DoLeg(int gas, int i, int gasTankSize)
{
  gas += gasOnStation[i];
  if (gas > gasTankSize) gas = gasTankSize;
  gas -= gasDrivingCosts[i];
  return gas;
}

Per prima cosa, guardiamo al caso in cui non abbiamo un serbatoio di gas con un massimo.

Essenzialmente, nel primo ciclo, guidiamo il cerchio intorno, senza preoccuparci se il nostro serbatoio del carburante ha carburante negativo o meno. Il punto è che non importa da dove inizi, la differenza tra quanto c'è nel tuo serbatoio del carburante all'inizio (0) e alla fine è lo stesso.

Pertanto, se finiamo con meno carburante di quanto abbiamo iniziato (quindi meno di 0), questo accadrà non importa da dove iniziamo, e quindi non possiamo fare un giro completo.

Se ci ritroviamo con almeno tanto carburante quanto abbiamo iniziato dopo aver fatto il giro completo, cerchiamo il momento in cui il serbatoio del carburante si trova nel punto più basso (che è sempre uguale a quello di una stazione di servizio). Se iniziamo a questo punto, non avremo mai meno carburante rispetto a questo punto (perché è il punto più basso e perché non perdiamo carburante se guidiamo un cerchio).

Pertanto, questo punto è una soluzione valida e, in particolare, esiste sempre un tale punto.

Ora esamineremo la versione in cui il nostro serbatoio di gas può contenere solo un quantitativo di gas.

Supponiamo che durante il nostro test iniziale (descritto sopra) abbiamo scoperto che non è impossibile fare l'intero cerchio. Supponiamo che iniziamo alla stazione di servizio i , carri armati alla stazione di benzina j , ma il nostro serbatoio del gas finisce per essere pieno, quindi perdiamo un po 'di gas in più che la stazione ha a disposizione. Quindi, prima di arrivare alla stazione k , finiamo per non avere abbastanza carburante, a causa del gas che abbiamo perso.

Affermiamo che in questo scenario, questo finirà per accadere, non importa da dove inizi. Supponiamo di iniziare alla stazione l .

Se l è tra j e k , allora ci fermiamo (molto tempo) prima che possiamo arrivare alla stazione k perché abbiamo iniziato da una cattiva stazione, o avremo sempre al massimo la quantità di carburante che avevamo quando abbiamo iniziato a i quando proviamo a raggiungere k , perché abbiamo attraversato le stesse stazioni (e il nostro serbatoio era pieno quando abbiamo passato j ). In entrambi i casi è male.

Se l non è tra j e k , allora ci fermiamo (a lungo) prima che arriviamo a j , o arriviamo a j con al massimo un serbatoio pieno, il che significa che non riusciremo nemmeno a k . In entrambi i casi è male.

Questo significa che se facciamo un giro partendo da un punto più basso proprio come nel caso del serbatoio di benzina infinitamente grande, allora ci riusciremo, oppure falliremo perché il nostro serbatoio del gas è troppo piccolo, ma questo significa che lo faremo fallire, non importa quale stazione selezioniamo per prima, il che significa che l'istanza non ha soluzione.

Sembra una derivazione dell'algoritmo del percorso più breve, quindi in pratica consideri ciascuna stazione come un vertice di un grafico, e i bordi sono pesati alla loro distanza (in termini di carburante).

Quindi puoi utilizzare un adattamento di Dijkstra per risolverlo - > link

La mia prima risposta sarebbe "I requisiti sembrano essere incompleti, sei sicuro che vuoi che io scriva il codice basandomi solo su questi requisiti, li inventeremo mentre andiamo, o vorresti che il mio aiuto completasse i requisiti? prima di progettare il software? ".

Le richieste incomplete sono, come affermato in altre domande, Capacità di carburante della macchina. Punto finale: è il punto iniziale o la stazione prima del punto iniziale. (Penso che tu risponda a questo nel tuo commento "completare un cerchio completo implica end = start, in tal caso. Vorrei chiarire questo come non è esplicito) La domanda implica che esiste una soluzione, e solo una, è corretta.

Altri problemi Le prestazioni dell'algoritmo sono un problema o, in altre parole, qual è il budget per questo progetto.

È una buona domanda: non puoi rispondere nella sua forma attuale ed essere certo di aver fornito al cliente la soluzione al problema che si aspetta.

Credo che al quiz dato manchino alcune parti vitali. Tuttavia, nel mio ragionamento vorrei usare le seguenti ipotesi:

• Il serbatoio dell'auto ha una capacità di carburante illimitata
• È possibile viaggiare solo in senso orario
• L'auto inizia con 0 gas
• La macchina dovrebbe finire nello stesso distributore di benzina

Dati questi presupposti, l'attività può essere facilmente forzata brutale con complessità O (n ** 2), provando tutte le stazioni di servizio.

Se è necessaria una soluzione più robusta, è possibile trasformare questo quiz in problema di sub-sequenza continuo massimo con vincoli extra, che non dovrebbe andare sotto lo zero. La complessità di questo algoritmo è O (n) - lineare.

Per il primo passo, trasformiamo il nostro problema iniziale in un problema che è risolvibile mediante la massima sotto-sequenza sommando la quantità di gas alla stazione di servizio e il costo di andare a quella stazione.

Il secondo passaggio consiste nell'applicare l'algoritmo di sub-sequenza massimo. L'algoritmo si basa su 2 presupposti:

• se il contatore di gas è andato sotto lo 0, è sempre meglio riavviare dalla stazione di servizio attuale
• altrimenti è meglio riempire il serbatoio, dato che qui c'è più di 0 gas

Applicando questo algoritmo alla lista cerchiata delle stazioni 2 volte (2 sequenze sovrapposte), otterremo la stazione che avvia la sequenza che accumula la maggior parte del carburante.

Il terzo passo è verificare che l'obiettivo sia raggiungibile con una data quantità di carburante e data stazione di partenza, complessità o (n)

Di seguito è riportata una descrizione di come penso possa funzionare. Non posso affermare che questa è l'unica soluzione. Non l'ho provato a fondo, quindi ti lascio questo per verificare.

In realtà penso che sia troppo difficile venire fuori durante un'intervista.

L'illustrazione allegata mostra l'idea generale. La variabile x rappresenta il nodo corrente in esame.

Utilizzaquestaformulaseseiperilprimonodo.

Utilizza questa formula per i nodi x = 2, ..., N

ogni nodo ha una quantità di gas g (x) e la distanza dal nodo x al nodo successivo è data da d (x, x + 1)

Il R.H.S dell'equazione di cui sopra dovrebbe essere la distanza tra gli ultimi due nodi in una rotta.

Si inizia generando una permutazione di percorsi validi - Esempio:

percorso 1: A, B, C, D, A

Percorso 2: B, C, D, A, B

percorso 3: C, D, A, B, C

percorso 4: D, A, B, C, D

L'idea è che per ogni percorso, a qualsiasi nodo x di una determinata rotta, è necessario calcolare se è possibile viaggiare verso il nodo successivo oppure no. Questo è determinato come segue:

[Passaggio 0] Controlla quanto gas hai finora + il gas massimo che puoi utilizzare dalla stazione corrente se l'importo di cui sopra consente di raggiungere la stazione successiva, aggiungere questo nodo al percorso.

[Passaggio 1] se l'importo di cui sopra non è sufficiente, il punto di inizio attuale è negativo, prova un'altra rotta.

Ora, per calcolare la quantità di gas che hai a un nodo x, supponi che per ogni unità di gas che consumi, viaggi 1 unità di distanza, fai questo:

Somma tutto il gas riempito da ogni arresto del gas (g1 + g2 + ... + g (x-1)) - Somma tutte le distanze percorse (d1 + d2 + ... + d (x-1)) + Aggiungi a quanto sopra due somme il gas in questa stazione (g (x))

Esempio 1 - Utilizzo dei dati forniti:

percorso 1, A, B, C, D

Calcolo B (1):

g (1) = 4

d (1,2) = 5

B (1) = falso. Questo significa che scegliere la rotta A, B, C, D non è buona dato che se inizi da A, non avrai abbastanza benzina per andare a B.

Esempio 2:

percorso 2, B, C, D, A

Calcolo B (1):

g (1) = 48

d (1,2) = 45

g (1) < = d (1,2) è falso, quindi B (1) = falso che significa che a partire da B sta lavorando finora. Continua ad esaminare la situazione al prossimo nodo (C)

g (2) = 50

d (2,3) = 44

g (1) -d (1,2) = 48-45

Ora

50 + (48-45) < = (d (2,3) = 44) è falso, quindi B (2) è falso, questo significa che iniziare da B e arrivare a C sta funzionando finora. Continua i test per vedere lo stato al prossimo nodo (D)

È un po 'tardi, ma proporrei un metodo per tentativi ed errori. (Non considero il contesto dell'intervista e il chiarimento della domanda sui requisiti.)

Cominciamo dalla stazione k e guidiamo verso la stazione più lontana che possiamo. Se raggiungiamo N + k = k di nuovo (siamo in modulo aritmetico modulare N , quindi 0 = < em> N , 1 = N + 1 , ecc.), quindi ci siamo riusciti.

Ma supponiamo di non poter raggiungere di nuovo k , ma solo l con k < = l < N + k . Male. Avremmo dovuto iniziare prima di k . Proviamo da k-1 . Se non possiamo raggiungere k , prova da k-2 , k-3 , ...

Ci sono due possibilità:

(1) Sfortunatamente, non riusciamo a raggiungere k da k-1 , da k-2 , ..., e infine da kN = k . Non c'è modo di riuscire, abbiamo provato ogni possibile benzina iniziale della strada.

(2) Oppure troviamo k ' < k che ci dà abbastanza gas per raggiungere k . Da k , raggiungiamo l e forse anche un l ' > l (se avessimo abbastanza benzina nella stazione k ). Forse potremmo persino raggiungere k ' di nuovo: ci siamo riusciti (a) . Se questo non è il caso, [k ', l'] è nondimeno un superset appropriato di [k, l] , perché k ' < k e l ' > = l (b) .

Se non siamo scoraggiati, allora possiamo applicare lo stesso metodo più e più volte (mantenendo il limite N + k ), e troveremo una sequenza di percorsi, ognuno di questi percorsi essendo più lungo (ha più stazioni di servizio) rispetto al precedente. Fino a quando non soddisfiamo la condizione (1) (errore) o condizione (2) (a) (successo).

Quando pensiamo di codificare questo semplice algoritmo, vediamo che il costo del percorso da k a l viene calcolato una sola volta. Quindi dobbiamo calcolare il costo della nuova parte del percorso (da k ' a k e da l a l ') ad ogni passaggio. Penso che sia ragionevolmente veloce.

Nota : come indicato in alcune altre risposte, questo problema è una versione semplice di un problema più complesso che coinvolge grafici, vedi link .

Spero che ti aiuti.

EDIT : ecco una implementazione della soluzione di cui sopra con serbatoio del gas limitato. Utilizza solo un ciclo, quindi è leggermente più lento quando non c'è abbastanza gas nelle stazioni, ma più veloce in qualsiasi altro caso. Sono sicuro che sia più comprensibile della spiegazione letterale.

int FindStartingPointInOneLoop(int[] gasOnStation, int[] gasDrivingCosts, int gasTankSize)
{
  // Assume gasOnStation.length == gasDrivingCosts.length
  int n = gasOnStation.length;
  bool move_forward = true;
  int k = 0;
  int l = 0;
  int gas = 0;
  while (true) {
    if (move_forward) { // try to move forward
      gas = DoLeg(gas, l, gasTankSize);
      if (gas < 0) { // we're out of gas : let's try a new start
        move_forward = false;
      }
      l = (l+1) % n;
    } else { // try to start from a previous gas station
      k = (k-1) % n;
      if (k == 0) { // that was a complete round without any adequate start
        Console.WriteLine("Instance does not have a solution.");
        return -1;
      }
      gas = DoLeg(gas, k, gasTankSize);
        if (gas >= 0) { // we reached our start point, let's try to move forward with the optional extra gas
          move_forward = true;
      }
    }
    if (l == k && gas >= 0) { // we joined "head" and "tail"
      return k;
    }
  }  
}
int DoLeg(int gas, int i, int gasTankSize)
{
  gas += gasOnStation[i];
  if (gas > gasTankSize) gas = gasTankSize;
  gas -= gasDrivingCosts[i];
  return gas;
}