12306 발 표 알고리즘 단상

머리말
휴일 인파 가 몰 릴 때마다 12306 이 화제 가 되 고 2016 년 설 도 예 외 는 없다.섣달 그믐날 탕 설화 (NetFocus) 일행 등 과 QQ 그룹 에서 12306 표 구 매 문 제 를 둘러싸 고 열 띤 토론 을 벌 였 다.마지막 으로 표 구 매 문 제 는 생각 보다 복잡 하기 때문에 결국은 공 설 이 공리 적 이 고 할머니 가 일리 가 있다 고 말 하 며 비교적 뚜렷 하고 명확 한 결 과 를 얻 지 못 했다.그래서 붓 을 들 어 자신의 이 해 를 이야기 하기 로 했 는데 중요 한 것 은 표를 구 매 요청 에 직면 했 을 때 표를 낼 수 있 는 지 없 는 지 를 해결 하 는 것 이다.만약 나의 방법 에 빈틈 이 있다 면, 반드시 지적 해 주 십시오. 감사합니다!
설명 이 필요 한 것 은 제 이산 수학 과 조합 수학 지식 을 체육 선생님 께 일찍 돌려 드 렸 기 때문에 아래 의 이 알고리즘 은 여러분 들 이 직시 할 수 없 을 정도 로 거 칠 고 제 생각 을 온전 하 게 표현 하 기 를 바 랍 니 다.
출 표 규칙 억측
오랫동안 기 차 를 타 본 적 이 없고 12306 에서 표를 산 적 이 없 기 때문에 저 는 관련 글 에 따라 다음 과 같은 발 표 규칙 을 가상 해 냈 습 니 다.
기차 K110 이 a 에서 출발 하여 bcd 세 역 을 거 쳐 최종 적 으로 종점 e 로 간다 고 가정 합 니 다.그러면 승객 들 이 구 매 할 수 있 는 것 은 {ab, ac, ad, ae, bc, bd, be, cd, ce, de} 이라는 10 가지 '구간' 의 승차권 을 포함한다.
열차 탑승 인원 상한 선 이 500 명 이 라 고 가정 하면 500 명의 승객 이 ae 전 구간 의 승차권 을 구 매 했다 면 그 후 어느 구간 의 승차권 도 한 장 더 팔 수 없다.만약 에 499 명의 승객 이 ae 전과정 여객 표를 구 매 했다 면 또 다른 가능성 이 있다. 하 나 는 ae 전과정 여객 표를 한 장 더 사서 열 차 를 처음부터 종점 까지 만재 하 는 것 이다.둘째, ae 에 포 함 된 ab / ac / ad / bc / bd / be / cd / ce / de 는 각 구간 에서 최대 1 장의 승차권 만 판매 할 수 있 습 니 다. 이때 먼저 내 린 다음 에 원칙 적 으로 구간 간 에 서로 교차 되 어 서 는 안 됩 니 다. 앞의 구간 에서 사람 이 내 려 야 뒤의 구간 에서 사람 이 탈 수 있 습 니 다.예 를 들 어 우 리 는 ab 1 장, bc 1 장, cd 1 장, de 1 장의 조합 또는 ac 1 장, ce 1 장의 조합 도 동시에 발행 할 수 있다.반면에 이때 ac, bd, cd 가 각각 1 장 씩 발행 되면 열 차 는 b 역 에 도착 할 때 만 선 이 고 bd 를 가 진 사람 은 탈 수 없 으 며 c 역 에 도착 할 때 ac 를 가 진 사람 은 내 릴 수 있 기 때문에 cd 를 가 진 사람 은 탈 수 있다.
그 렇 기 때문에 우리 가 특정한 구간 의 객 표를 팔 때마다 다른 구간 의 매 표 가능 수량 에 상응하는 변 화 를 일 으 킬 수 있다.따라서 같은 번호 의 열차 라 도 날짜 에 따라 운행 횟수 내 에 판 매 된 승차권 총 수 는 승객 의 티켓 구 매 구간, 티켓 구 매 수량 에 따라 완전히 다르다.자세히 살 펴 본 결과 열차 가 출발 에서 종점 까지 의 전체 과정 에서 유일 하 게 변 하지 않 는 것 은 열차 가 가장 많이 수용 할 수 있 는 인원 인 '적재 인원' 이라는 것 을 발견 했다.
적재 인원
'적재 인원' 이라는 개념 을 도입 한 것 은 좌석 과 차표 간 의 관 계 를 정리 하기 위해 서다.
내 가 몇 년 전에 기 차 를 탄 경험 으로 볼 때, 만약 열차 에 아직 빈 좌석 이 있다 면, 우 리 는 표를 구입 한 후에 객차 번호, 좌석 번 호 를 인쇄 한 차 표를 얻 을 수 있 을 것 이다.만약 좌석 이 이미 매진 되 었 다 면, 열차 의 적재 인원 이 아직 그 부하 안에 있다 면, 우 리 는 여전히 차표 한 장 을 구 매 할 수 있 고, 이 를 통 해 역 에 들 어가 서 차 를 탈 수 있다. 비록 이 표 는 차례 만 기재 되 어 있 지만, 구체 적 인 객차 번호 와 좌석 번 호 는 없다.이것 이 바로 "좌석 표 가 있다" 와 "좌석 표 가 없다" 의 유래 이다.
이 로 인해 파생 된 판매 좌석 번 호 는 시스템 에서 회수 한 후에 후속 구간 의 승객 에 게 판매 하 는 지 여 부 는 우리 의 토론 을 방해 하 는 문제 중 하나 가 되 었 다.나 는 시스템 이 좌석 번 호 를 회수 하지 않 는 다 고 가정 했다.즉, 갑 이 a 에서 b 까지 좌석 이 있 고 마지막 좌석 이 라 고 가정 하면 15 칸 102 번 좌석 이다.그리고 을 은 그 후에 b 에서 d 까지 의 표를 샀 기 때문에 시스템 은 이 좌석 15 - 102 를 을 에 게 다시 판매 하지 않 았 다.갑 이 b 에서 내 린 후에 객차 에 자리 가 없 는 다른 승객 들 이 스스로 차지 하여 사용한다.
토론 을 통 해 나 는 실제 좌석 번 호 를 회수 할 지 말 지 에 얽 매 이 는 것 이 큰 잘못 이라는 것 을 깨 달 았 다.좌석 번호 가 없 는 것 도 가상 좌석 으로 본다 면 열차 의 경우 만재 와 만재 되 지 않 은 두 가지 상황 만 구분 해 야 한다. 만재 시 에는 표를 팔 수 없고 만재 되 지 않 았 을 때 는 후속 구간 의 표를 팔 수 있다.전체 열차 가 실 을 수 있 는 인원 이나 부하 라 고 할 수 있 는 인원 은 항상 상수 일 것 이다.
이런 설정 하에 서 발 권 여 부 는 열차 가 특정 구간 에서 과 적 여 부 를 판단 하 는 문제 로 바 뀌 었 다.'좌석 표 가 있다' 와 '좌석 표 가 없다' 는 것 은 자 연 스 럽 게 부차적인 문제 로 퇴화 되 었 다.
고속 철도 와 동 차 에 대해 서 는 아직 타 본 적 이 없 기 때문에 차량 적재 설비 의 동기 화 능력 이 기 존 기차 보다 훨씬 강하 기 때문에 열차 승무원 이나 다른 체 제 를 빌려 빈 좌석 번호 회수 와 업 데 이 트 를 실현 하 는 것 은 어 려 운 문제 가 아 닐 것 이 라 고 추측 할 수 밖 에 없다.
총체 적 사고방식
내 가 처음에 대학의 과정 에서 은행 줄 서기 에 관 한 알고리즘 시 뮬 레이 션 이 있 었 는데 나의 영감 은 바로 여기에 있 었 다.
나의 방법 은 이러한 전제 에서 세 워 졌 다. "임의의 시간 에 열 차 는 모두 적재량 을 초과 해 서 는 안 된다. 열차 에 실 린 승객 수 는 예 정 된 적재량 을 초과 해 서 는 안 된다."
이 를 원칙 으로 나 는 열차 의 운행 을 모 의 하여 열차 가 출발 역 에서 출발 하여 각 역 에서 승객 을 오 르 내 리 며 마지막 으로 종점 까지 운전 하 게 할 것 이다.그 동안 저 는 열차 가 각 역 에 정차 할 때의 승객 수 를 추적 할 것 입 니 다. 과 적 현상 이 발견 되면 표 발행 에 문제 가 생 겨 팔 지 말 아야 할 표를 팔 았 다 는 것 을 설명 합 니 다.이 를 통 해 나 는 "표 한 장 을 내 려 면 열차 가 과 적 되 지 않도록 해 야 한다" 는 결론 을 내 릴 수 있다.
그래서 나의 방법 은 본질 적 으로 미로 문제 의 귀환 이나 궁 거 와 유사 하 다.구체 적 으로 다음 과 같이 설명 할 수 있다.
한 노선 이 티켓 구 매 요 구 를 받 았 을 때, 그것 은 티켓 구 매 구간 과 구 매 예정 수량 으로 모든 사이트 의 이미 판 매 된 표 수 를 한 번 훑 어 보 며 실제 승객 의 상하 차 상황 을 모 의 한다.옮 겨 다 녀 도 과 적 되 지 않 는 다 면 티켓 구 매 요청 에 동의 할 수 있다 는 뜻 이다.옮 겨 다 니 는 동안 어떤 사이트 가 과부하 되 는 것 을 발견 하면 이 티켓 구 매 요 구 를 거절 해 야 한다.
상기 절 차 를 바탕 으로 병발 상황 에 직면 할 때 먼저 전체 노선 을 하나의 집합 전체 로 보고 이 노선 의 서로 다른 구간 에 대한 구 매 요 구 를 하나의 요청 대열 에 넣 은 다음 에 FIFO 의 원칙 에 따라 순서대로 처리 해 야 한다.처리 과정 에서 제 가 필요 한 것 은 모든 구간 의 매 표 수 를 한 번 읽 고 표를 낼 수 있 는 지 에 대한 결정 을 내 린 다음 에 그 중에서 매 표 요청 에 대응 하 는 구간 의 매 표 수 를 수정 하 는 것 입 니 다.
모 의 열차 운행
스칼라 의 간결 하고 효율 적 이기 때문에 나 는 그것 을 선택 했다.다른 한편, 제 가 최근 에 심취 하고 있 기 때문에 앞으로 도 스칼라 로 12306 표를 모 의 하 는 시간 이 있 기 를 바 랍 니 다.그러나 나 는 이곳 의 코드 가 매우 조잡 하 다 는 것 을 알 고 있다. 심지어 역 의 도착 시간 과 발차 시간 까지 나 는 Float 시 뮬 레이 션 을 했다. 왜냐하면 나 는 스칼라 에서 C \ # 리 Timespan 를 무엇으로 표시 하 는 지 아직 모 르 기 때문이다. 하하.
STEP 1: 사이트 스테이션, 구간 간격, 라인 정의

case class Station(val name: String, val arrival: Float, val depart: Float) {
  require(arrival <= depart)

  def prior(that: Station): Boolean = this.depart < that.arrival
  def after(that: Station): Boolean = this.arrival > that.depart
}

case class Interval(val begin: Station, val end: Station) {
  require(begin prior end)
}

case class Line(val stations: List[Station]) {
  require(stations.length >= 2)
}

STEP 2: 정의 열차 Train
열 차 는 두 가지 간단 한 방법 이 있다.그것들 은 모두 적재량 을 초과 할 때 이상 을 던 질 것 이다.

class Train(val capacity: Int) {
  var load: Int = 0;

  def land(amount: Int): Unit = {
    load -= amount
    if (load < 0)
      throw new IllegalArgumentException("Train loading should not be negative.")
  }

  def board(amount: Int): Unit = {
    load += amount
    if (load > capacity)
      throw new IllegalArgumentException("Train is overloading.")
  }
}

STEP 3: 예매 센터 예약 정의
예매 센터 는 발 표를 책임 지 는 곳 이다.이 는 먼저 노선 의 사이트 목록 에 따라 모든 구간 을 포함 하 는 목록 intervals 을 만 든 다음 에 각 구간 의 매 표 sold 를 모두 0 으로 초기 화 합 니 다.그리고 티켓 팅 방법 sell(interval: Interval, amount: Int) 을 정 의 했 습 니 다. 구간 인 터 벌 에서 amount 표를 팔 고 이 구간 에서 매 표 된 수량 을 업데이트 합 니 다.

class Booking(val line: Line, val train: Train) {
  val intervals: IndexedSeq[Interval] = for {
    begin <- line.stations.indices dropRight 1
    end <- line.stations.indices drop begin + 1
  } yield Interval(line.stations(begin), line.stations(end))

  val sold: mutable.Map[Interval, Int] = intervals.map(i => i -> 0)(collection.breakOut)

  override def toString(): String = {
    (for (i <- intervals) yield s"${i.begin.name}${i.end.name}[${sold(i)}]").mkString("  ")
  }

  def sell(interval: Interval, amount: Int) = {
    sold(interval) += amount
  }
}

4 단계: 아 날로 그 드라이브 Watcher 정의
Watcher 의 핵심 방법 은 runTrain() 열차 가 출발 역 에서 출발 해 종점 으로 향 하도록 하 는 것 이다.그 동안 각 역 에 도 착 했 을 때 '먼저 내 린 다음 에 올 라 가 는' 원칙 을 모 의 하여 열차 에 실 린 승객 수 를 업데이트 합 니 다.각 역 의 상하 인원 은 판 매 된 승차권 에 따라 내 린 것 이다. 내 린 것 은 이 역 을 종점 으로 하 는 모든 승차권 을 합 친 것 이 고 이 역 을 기점 으로 하 는 모든 승차권 을 합 친 것 이다.

class Watcher(val booking: Booking) {
  def runTrain() = {
    for (
      s <- booking.line.stations
    ) {
      print(s"Train arrived [${s.name}]: ")

      booking.train land land(s)
      booking.train board board(s)
      printf("-[%3d] +[%3d] ", land(s), board(s))

      println(s"= ${booking.train.load}")
    }
  }

  def land(station: Station): Int = {
    var amount: Int = 0
    for {i <- booking.intervals
         if i.end == station
    } amount += booking.sold(i)
    amount
  }

  def board(station: Station): Int = {
    var amount: Int = 0
    for {i <- booking.intervals
         if i.begin == station
    } amount += booking.sold(i)
    amount
  }
}

STEP 5: 열 차 를 잠시 달리 게 한다.
마지막 으로 나 는 ABCDE 총 5 개의 역 을 모 의 해 100 명 으로 가득 찬 열차 한 대 를 타고 5 개의 구간 의 표를 팔 았 다.

object Railway {
  def main(args: Array[String]) = {
    val line = new Line(List(
      Station("A", 1.0f, 1.0f),
      Station("B", 2.0f, 2.1f),
      Station("C", 3.0f, 3.1f),
      Station("D", 4.0f, 4.2f),
      Station("E", 5.0f, 5.0f)
    ))
    val train = new Train(100)
    val booking = new Booking(line, train)
    val watcher = new Watcher(booking)

    print("Line route[interval]: ")
    print((for (s <- line.stations) yield s.name).mkString(" -> "))
    println(s"\t[${booking.intervals.length}]")

    try {
      booking.sell(booking.intervals(0), 3)
      booking.sell(booking.intervals(4), 20)
      booking.sell(booking.intervals(3), 30)
      booking.sell(booking.intervals(6), 35)
      booking.sell(booking.intervals(9), 35)

      println(booking)
      watcher.runTrain()
    } catch {
      case e: IllegalArgumentException => println(e.getMessage)
    }
  }
}

다음 출력 을 가 져 옵 니 다:

첫 번 째 줄 은 선로 도 이 고 괄호 안에 포 함 된 구간 총수 이다.

두 번 째 줄 은 이미 판 매 된 승차권 상황 이 고 구간 [표 수] 이다.

뒤의 몇 줄 은 모 의 열차 운행 시 상하 여객 의 상황

이다.

Line route[interval]: A -> B -> C -> D -> E [10]
AB[3]  AC[0]  AD[0]  AE[30]  BC[20]  BD[0]  BE[35]  CD[0]  CE[0]  DE[35]
Train arrived [A]: -[  0] +[ 33] = 33
Train arrived [B]: -[  3] +[ 55] = 85
Train arrived [C]: -[ 20] +[  0] = 65
Train arrived [D]: -[  0] +[ 35] = 100
Train arrived [E]: -[100] +[  0] = 0

만약 파 는 표 에 문제 가 있다 면 아래 와 같이:

AB[3]  AC[0]  AD[0]  AE[50]  BC[20]  BD[0]  BE[35]  CD[0]  CE[0]  DE[35]
Train arrived [A]: -[  0] +[ 53] = 53
Train arrived [B]: Train is overloading.

나 는 아직 다 쓰 지 못 했다.
이 부분 에서 나 는 위의 시 뮬 레이 션 프로그램 에 따라 반대로 해서 표를 파 는 구체 적 인 알고리즘 을 얻 을 것 이다.우선 현재 이 원 고 를 제출 하 세 요.시간 이 있 으 면 다시 완전 하 게 보충 하 겠 습 니 다.조판 에 관 해 서 는 최종 원고 가 끝 난 후에 하 자.마크 다운 으로 썼 습 니 다. cnblog 에 보 내기 전에 HTML 을 내 보 내 고 붙 여 넣 기 를 복사 해 야 합 니 다. 귀 찮 습 니 다.
마지막 에 쓰다
이에 비해 탕 은 그의 글 에서 간단 한 티켓 팅 방법 을 사용 했다. 이 방법의 전 제 는 '원자 구간 의 사용 가능 한 표 수 는 직원 이 차 를 초기 화 할 때 미리 설정 하 는 것' 이다. 구체 적 인 내용 은 개인 이 12306 의 핵심 사용자 에 게 요구 하 는 핵 모델 디자인 사고 와 구조 디자인 을 참고 하 는 것 이다.
표를 낼 때 재 고 를 줄 이 는 논 리 는 주문 정보 에 따라 출발지 와 목적 지 를 얻 은 다음 에 이 구간 의 모든 원자 구간 을 얻 는 것 이다.그리고 각 원자 구간 의 사용 가능 한 표 수 를 1 로 줄 이 고 모든 원자 구간 이 충분히 줄 어 들 면 표를 구 매 하 는 데 성공 한다.그렇지 않 으 면 표를 구 매 하 는 데 실패 하여 사용자 에 게 이 표 가 이미 다 팔 렸 음 을 알려 준다.