本文始發於個人公眾號：TechFlow，原創不易，求個關注

今天是算法和數據結構專題第25篇文章，我們繼續博弈論專題。

在上一篇文章當中我們了解了最簡單的巴什博奕，今天我們來看看另一個經典的博弈模型——威佐夫博弈。博弈論和機器學習有些類似，數學家們針對場景進行建模，設計出了幾個經典模型。然後我們在面臨具體問題的時候，對問題進行深入分析，尋找最合適的模型應用來解決它。

石子問題

我們來看一道經典的例題，有兩堆石子，有兩個絕頂聰明的人在玩一個遊戲。每次每個人可以從其中一堆石子當中取走任意數量的石子，或者是從兩堆當中同時取走相同數量的石子。無法取石子的人落敗，請問，在告知兩堆石子數量的情況下，這兩個人當中哪一方會獲勝？

我們簡單分析一下，會發現一些局面是先手必敗的。比如說(0, 0)，再比如(1, 2)。我們簡單分析一下(1, 2)，先手有4種策略，首先他可以取走第一堆，那麼後手可以取完第二堆，顯然後手獲勝。他也可以在第二堆當中取1個，這時剩下(1, 1)，後手會同時取完，同樣是後手獲勝。第三種是他取走第二堆，後手可以取完第一堆，後手獲勝。第四種是他在第一堆和第二堆當中同時取走一個，這時第二堆剩下一個，後手勝。

那麼，這些必敗的狀態之間有什麼規律呢？我們怎麼找到這個規律，並且找到解呢？

分析

我們可以枚舉幾個必敗的狀態：(0, 0), (1, 2), (3, 5), (4, 7)…

我們觀察一下這些狀態，可以找到兩條規律。我們假設從小到大排的第k個必敗狀態是(x, y)，並且x < y。我們可以發現y = x + k。也就是說必敗狀態兩個數的差值是遞增的，這也說明了每一個必敗狀態的差值都各不相同。

其實這是很容易證明的，我們用反證法，假設(a, a+k), (b, b+k)都是必敗狀態，並且a < b。那麼先手在面臨(b, b+k)的時候，只需要在兩堆當中同時取走b-a個石子，那麼給後手的局面就是(a, a+k)。對於後手來說，這是一個必敗的局面，這就和(b, b+k)先手必敗矛盾，所以不存在兩個必敗局面的差值相等。

我們也可以作圖分析，我們把兩堆石子的數量看成是坐標軸上的一個點。所以遊戲就變成了：棋盤上有一個點，每次每個人可以將它向下、向左或者向左下移動若干個格子，不能移動的人輸。終止節點顯然是原點，一步就能移動到原點的點顯然是必勝點，假設我們給這些所有必勝點都染色的話，剩下的的沒當中橫縱坐標和最小的點就是下一個必敗點。因為它不論如何移動，都會給對手留下一個必勝點。

我們根據上面的邏輯把必敗點都染色，可以得到下面這張圖：

從這張圖可以看出，必敗點之間不能通過一次移動得到，換句話說可以一次移動到必敗點的點都是必勝點，從圖上可以看出，除了必敗點的之外的點都是必勝點，並且每一個自然數都必然只會被包含在一個必敗狀態當中。

到這裏，我們距離解法已經很接近了，現在剩下的問題是，我們如何根據x和y的取值快速判斷它們是否構成一個必敗局面呢？也就是說我們能不能找出一個通項公式，對於第k個必敗局面，它的坐標是(\(x_k, y_k\))呢？

求解

為了寫出通項公式，我們需要引入Betty定理。

設a和b是兩個正無理數，並且\(\frac{1}{a} + \frac{1}{b} = 1\)

記P={[\(a_n\)], \(n \in N^+\)}, Q={[\(b_n\)], \(n \in N^+\)}，則\(P \cap Q = \varnothing\)，\(P\cup Q = N^+\)

證明

\(P\cap Q = \varnothing\)

反證，我們假設存在\(k \in P\)並且\(k \in Q\)，即存在正整數n， m滿足 k < an, bm < k+1。

也就是：\(\frac{n}{k} > \frac{1}{a} > \frac{n}{k+1}, \frac{m}{k} > \frac{1}{b} > \frac{m}{k+1}\)兩個式子相加可以得到：\(\frac{m+n}{k} > 1 > \frac{m+n}{k}\)

即\(k < n+m < k+ 1\)，這與n，m，k都是正整數矛盾

\(P \cup Q = N^+\)

反證，假設存在\(k \notin P\)且\(k \notin Q\)，即存在正整數n，m滿足\(an < k < a(n+1)-1, bm < k < b(m+1)-1\)

即：\(\frac{n}{k} < \frac{1}{a} < \frac{n+1}{k+1}, \frac{m}{k} < \frac{1}{b} < \frac{m+1}{k+1}\)

相加，可以得到：\(\frac{m+n}{k} < 1 < \frac{n+m+2}{k+1}\)

即：n + m < k < n + m + 1，這與n，m，k均為正整數矛盾

我們花了這麼大力氣來證明Betty定理就是為了用的，因為我們發現必敗狀態的通項和Betty定理序列很像。我們不妨假設存在這樣的a, b同時滿足Betty定理與必敗狀態的性質：

\[[an] + n = [bn], \frac{1}{a} + \frac{1}{b} = 1 \]

\[[an] + n = [an + n] = [(a+1)n] = [bn] \]

代入可以得到：

\[\frac{1}{a} + \frac{1}{a+1} = 1 \]

解這個方程，可以得到\(a = \frac{1 + \sqrt{5}}{2}\approx 1.618\)，熟悉數學的同學相信一下就看出來了，這個數是黃金分割的比例，這是巧合嗎，還是藏着更深的道理呢？

至少，求出了a之後，我們就可以非常簡單地判斷必敗狀態了：

import math
def lose_or_win(a, b):
    if a > b:
        a, b = b, a
    
    k = b - a
    # 根據差值k求出第k個必敗狀態，判斷是否相等
    return not (int(k * (math.sqrt(5)+1) / 2)) == a

總結

和之前介紹的巴什博奕相比，威佐夫博弈的推導過程要複雜得多，但是雖然推導過程依然複雜，但是仍然擋不住最後實現的代碼非常簡單。

另外，在推導的過程當中，我們用到了Betty定理，這個定理的推導和證明雖然不難，但是如果不是數學專業的同學，可能大概率都沒有接觸過。這其實體現了博弈論本身和數學的關係是非常緊密的。一個看起來非常簡單的問題，引申出了一系列眼花繚亂的推導和證明，怎麼樣，大家看得還過癮嗎？

今天的文章到這裏就結束了，如果喜歡本文，可以的話，請點個關注，給我一點鼓勵，也方便獲取更多文章。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!

※綠能、環保無空污,成為電動車最新代名詞，目前市場使用率逐漸普及化

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※教你寫出一流的銷售文案?

前言

在使用Spring和SpringMVC的老版本進行開發時，我們需要配置很多的xml文件，非常的繁瑣，總是讓用戶自行選擇配置也是非常不好的。基於約定大於配置的規定，Spring提供了很多註解幫助我們簡化了大量的xml配置；但是在使用SpringMVC時，我們還會使用到WEB-INF/web.xml，但實際上我們是完全可以使用Java類來取代xml配置的，這也是後來SpringBoott的實現原理。本篇就來看看Spring是如何實現完全的零XML配置。

正文

先來看一下原始的web.xml配置：

<!DOCTYPE web-app PUBLIC
 "-//Sun Microsystems, Inc.//DTD Web Application 2.3//EN"
 "http://java.sun.com/dtd/web-app_2_3.dtd" >

<web-app>
  <context-param>
    <param-name>contextConfigLocation</param-name>
    <param-value>
      <!--加載spring配置-->
      classpath:spring.xml
    </param-value>
  </context-param>
  <context-param>
    <param-name>webAppRootKey</param-name>
    <param-value>ServicePlatform.root</param-value>
  </context-param>

  <listener>
    <listener-class>org.springframework.web.context.ContextLoaderListener</listener-class>
    <!--<listener-class>org.springframework.web.context.request.RequestContextListener</listener-class>-->
  </listener>

  <servlet>
    <servlet-name>spring-dispatcher</servlet-name>
    <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
    <init-param>
      <!--springmvc的配置文件-->
      <param-name>contextConfigLocation</param-name>
      <param-value>classpath:spring-dispatcher.xml</param-value>
    </init-param>
    <load-on-startup>0</load-on-startup>
  </servlet>
  <servlet-mapping>
    <servlet-name>spring-dispatcher</servlet-name>
    <url-pattern>/</url-pattern>
  </servlet-mapping>
</web-app>

這裏各個配置的作用簡單說下，context-param是加載我們主的sping.xml配置，比如一些bean的配置和開啟註解掃描等；listener是配置監聽器，Tomcat啟動會觸發監聽器調用；servlet則是配置我們自定義的Servlet實現，比如DispatcherServlet。還有其它很多配置就不一一說明了，在這裏主要看到記住context-param和servlet配置，這是SpringIOC父子容器的體現。在之前的I文章中講過IOC容器是以父子關係組織的，但估計大部分人都不能理解，除了看到複雜的繼承體系，並沒有看到父容器作用的體現，稍後來分析。
了解了配置，我們就需要思考如何替換掉這些繁瑣的配置。實際上Tomcat提供了一個規範，有一個ServletContainerInitializer接口：

public interface ServletContainerInitializer {
    void onStartup(Set<Class<?>> var1, ServletContext var2) throws ServletException;
}

Tomcat啟動時會調用該接口實現類的onStartup方法，這個方法有兩個參數，第二個不用說，主要是第一個參數什麼？從哪裡來？另外我們自定義的實現類又怎麼讓Tomcat調用呢？
首先解答最後一個問題，這裏也是利用SPI來實現的，因此我們實現了該接口后，還需要在META-INF.services下配置。其次，這裏傳入的第一個參數也是我們自定義的擴展接口的實現類，我們可以通過我們自定義的接口實現很多需要在啟動時做的事，比如加載Servlet，但是Tomcat又是怎麼知道我們自定義的接口是哪個呢？這就需要用到@HandlesTypes註解，該註解就是標註在ServletContainerInitializer的實現類上，其值就是我們擴展的接口，這樣Tomcat就知道需要傳入哪個接口實現類到這個onStartup方法了。來看一個簡單的實現：

@HandlesTypes(LoadServlet.class)
public class MyServletContainerInitializer implements ServletContainerInitializer {
    @Override
    public void onStartup(Set<Class<?>> set, ServletContext servletContext) throws ServletException {
        Iterator var4;
        if (set != null) {
            var4 = set.iterator();
            while (var4.hasNext()) {
                Class<?> clazz = (Class<?>) var4.next();
                if (!clazz.isInterface() && !Modifier.isAbstract(clazz.getModifiers()) && LoadServlet.class.isAssignableFrom(clazz)) {
                    try {
                        ((LoadServlet) clazz.newInstance()).loadOnstarp(servletContext);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                }
            }
        }
    }
}

public interface LoadServlet {

    void loadOnstarp(ServletContext servletContext);
}

public class LoadServletImpl implements LoadServlet {
    @Override
    public void loadOnstarp(ServletContext servletContext) {
        ServletRegistration.Dynamic initServlet = servletContext.addServlet("initServlet", "org.springframework.web.servlet.DispatcherServlet");
        initServlet.setLoadOnStartup(1);
        initServlet.addMapping("/init");
	}
}

這就是Tomcat給我們提供的規範，通過這個規範我們就能實現Spring的零xml配置啟動，直接來看Spring是如何做的。
根據上面所說我們可以在spring-web工程下找到META-INF/services/javax.servlet.ServletContainerInitializer配置：

@HandlesTypes(WebApplicationInitializer.class)
public class SpringServletContainerInitializer implements ServletContainerInitializer {
	@Override
	public void onStartup(@Nullable Set<Class<?>> webAppInitializerClasses, ServletContext servletContext)
			throws ServletException {

		List<WebApplicationInitializer> initializers = new LinkedList<>();

		if (webAppInitializerClasses != null) {
			for (Class<?> waiClass : webAppInitializerClasses) {
				// Be defensive: Some servlet containers provide us with invalid classes,
				// no matter what @HandlesTypes says...
				if (!waiClass.isInterface() && !Modifier.isAbstract(waiClass.getModifiers()) &&
						WebApplicationInitializer.class.isAssignableFrom(waiClass)) {
					try {
						initializers.add((WebApplicationInitializer)
								ReflectionUtils.accessibleConstructor(waiClass).newInstance());
					}
					catch (Throwable ex) {
						throw new ServletException("Failed to instantiate WebApplicationInitializer class", ex);
					}
				}
			}
		}

		if (initializers.isEmpty()) {
			servletContext.log("No Spring WebApplicationInitializer types detected on classpath");
			return;
		}

		servletContext.log(initializers.size() + " Spring WebApplicationInitializers detected on classpath");
		AnnotationAwareOrderComparator.sort(initializers);
		for (WebApplicationInitializer initializer : initializers) {
			initializer.onStartup(servletContext);
		}
	}

}

核心的實現就是WebApplicationInitializer，先看看其繼承體系

AbstractReactiveWebInitializer不用管，主要看另外一邊，但是都是抽象類，也就是說真的實例也是由我們自己實現，但需要我們實現什麼呢？我們一般直接繼承AbstractAnnotationConfigDispatcherServletInitializer類，有四個抽象方法需要我們實現：

    //父容器
    @Override
    protected Class<?>[] getRootConfigClasses() {
        return new Class<?>[]{SpringContainer.class};
    }

    //SpringMVC配置子容器
    @Override
    protected Class<?>[] getServletConfigClasses() {
        return new Class<?>[]{MvcContainer.class};
    }

    //獲取DispatcherServlet的映射信息
    @Override
    protected String[] getServletMappings() {
        return new String[]{"/"};
    }

	// filter配置
    @Override
    protected Filter[] getServletFilters() {
        MyFilter myFilter = new MyFilter();
        CorsFilter corsFilter = new CorsFilter();
        return new Filter[]{myFilter,corsFilter};
    }

這裏主要注意getRootConfigClasses和getServletConfigClasses方法，分別加載父、子容器：

@ComponentScan(value = "com.dark",excludeFilters = {
        @ComponentScan.Filter(type = FilterType.ANNOTATION,classes = {Controller.class})
})
public class SpringContainer {
}

@ComponentScan(value = "com.dark",includeFilters = {
        @ComponentScan.Filter(type = FilterType.ANNOTATION,classes = {Controller.class})
},useDefaultFilters = false)
public class MvcContainer {
}

看到這兩個類上的註解應該不陌生了吧，父容器掃描裝載了所有不帶@Controller註解的類，子容器則相反，但需要對象時首先從當前容器中找，如果沒有則從父容器中獲取，為什麼要這麼設計呢？直接放到一個容器中不行么？先思考下， 稍後解答。
回到onStartup方法中，直接回調用到AbstractDispatcherServletInitializer類：

	public void onStartup(ServletContext servletContext) throws ServletException {
		super.onStartup(servletContext);
		//註冊DispatcherServlet
		registerDispatcherServlet(servletContext);
	}

先是調用父類：

	public void onStartup(ServletContext servletContext) throws ServletException {
		registerContextLoaderListener(servletContext);
	}

	protected void registerContextLoaderListener(ServletContext servletContext) {

		//創建spring上下文，註冊了SpringContainer
		WebApplicationContext rootAppContext = createRootApplicationContext();
		if (rootAppContext != null) {
			//創建監聽器
			ContextLoaderListener listener = new ContextLoaderListener(rootAppContext);
			listener.setContextInitializers(getRootApplicationContextInitializers());
			servletContext.addListener(listener);
		}
	}

然後調用createRootApplicationContext創建父容器：

	protected WebApplicationContext createRootApplicationContext() {
		Class<?>[] configClasses = getRootConfigClasses();
		if (!ObjectUtils.isEmpty(configClasses)) {
			AnnotationConfigWebApplicationContext context = new AnnotationConfigWebApplicationContext();
			context.register(configClasses);
			return context;
		}
		else {
			return null;
		}
	}

可以看到就是創建了一個AnnotationConfigWebApplicationContext對象，並將我們的配置類SpringContainer註冊了進去。接着創建Tomcat啟動加載監聽器ContextLoaderListener，該監聽器有一個contextInitialized方法，會在Tomcat啟動時調用。

	public void contextInitialized(ServletContextEvent event) {
		initWebApplicationContext(event.getServletContext());
	}

	 */
	public WebApplicationContext initWebApplicationContext(ServletContext servletContext) {
		long startTime = System.currentTimeMillis();
		try {
			// Store context in local instance variable, to guarantee that
			// it is available on ServletContext shutdown.
			if (this.context == null) {
				this.context = createWebApplicationContext(servletContext);
			}
			if (this.context instanceof ConfigurableWebApplicationContext) {
				ConfigurableWebApplicationContext cwac = (ConfigurableWebApplicationContext) this.context;
				if (!cwac.isActive()) {
					// The context has not yet been refreshed -> provide services such as
					// setting the parent context, setting the application context id, etc
					if (cwac.getParent() == null) {
						// The context instance was injected without an explicit parent ->
						// determine parent for root web application context, if any.
						ApplicationContext parent = loadParentContext(servletContext);
						cwac.setParent(parent);
					}
					configureAndRefreshWebApplicationContext(cwac, servletContext);
				}
			}
			servletContext.setAttribute(WebApplicationContext.ROOT_WEB_APPLICATION_CONTEXT_ATTRIBUTE, this.context);

			ClassLoader ccl = Thread.currentThread().getContextClassLoader();
			if (ccl == ContextLoader.class.getClassLoader()) {
				currentContext = this.context;
			}
			else if (ccl != null) {
				currentContextPerThread.put(ccl, this.context);
			}

			return this.context;
		}
	}

可以看到就是去初始化容器，這個和之前分析xml解析是一樣的，主要注意這裏封裝了ServletContext對象，並將父容器設置到了該對象中。
父容器創建完成后自然就是子容器的創建，來到registerDispatcherServlet方法：

	protected void registerDispatcherServlet(ServletContext servletContext) {
		String servletName = getServletName();
		Assert.hasLength(servletName, "getServletName() must not return null or empty");

		//創建springmvc的上下文，註冊了MvcContainer類
		WebApplicationContext servletAppContext = createServletApplicationContext();
		Assert.notNull(servletAppContext, "createServletApplicationContext() must not return null");

		//創建DispatcherServlet
		FrameworkServlet dispatcherServlet = createDispatcherServlet(servletAppContext);
		Assert.notNull(dispatcherServlet, "createDispatcherServlet(WebApplicationContext) must not return null");
		dispatcherServlet.setContextInitializers(getServletApplicationContextInitializers());

		ServletRegistration.Dynamic registration = servletContext.addServlet(servletName, dispatcherServlet);
		if (registration == null) {
			throw new IllegalStateException("Failed to register servlet with name '" + servletName + "'. " +
					"Check if there is another servlet registered under the same name.");
		}

		/*
		* 如果該元素的值為負數或者沒有設置，則容器會當Servlet被請求時再加載。
			如果值為正整數或者0時，表示容器在應用啟動時就加載並初始化這個servlet，
			值越小，servlet的優先級越高，就越先被加載
		* */
		registration.setLoadOnStartup(1);
		registration.addMapping(getServletMappings());
		registration.setAsyncSupported(isAsyncSupported());

		Filter[] filters = getServletFilters();
		if (!ObjectUtils.isEmpty(filters)) {
			for (Filter filter : filters) {
				registerServletFilter(servletContext, filter);
			}
		}

		customizeRegistration(registration);
	}

	protected WebApplicationContext createServletApplicationContext() {
		AnnotationConfigWebApplicationContext context = new AnnotationConfigWebApplicationContext();
		Class<?>[] configClasses = getServletConfigClasses();
		if (!ObjectUtils.isEmpty(configClasses)) {
			context.register(configClasses);
		}
		return context;
	}

這裏也是創建了一個AnnotationConfigWebApplicationContext對象，不同的只是這裏註冊的配置類就是我們的Servlet配置了。然後創建了DispatcherServlet對象，並將上下文對象設置了進去。看到這你可能會疑惑，既然父子容器創建的都是相同類的對象，何來的父子容器之說？別急，這個在初始化該上文時就明白了。但是這裏的初始化入口在哪呢？沒有看到任何監聽器的創建和調用。實際上這裏的上下文對象初始化是在Servlet初始化時實現的，即init方法，直接來到HttpServletBean的init方法（分析SpringMVC源碼時講過）：

	public final void init() throws ServletException {
		...省略
		
		// Let subclasses do whatever initialization they like.
		initServletBean();
	}

	protected final void initServletBean() throws ServletException {
		try {
			this.webApplicationContext = initWebApplicationContext();
			initFrameworkServlet();
		}
	}

	protected WebApplicationContext initWebApplicationContext() {
		//這裡會從servletContext中獲取到父容器，就是通過監聽器加載的容器
		WebApplicationContext rootContext =
				WebApplicationContextUtils.getWebApplicationContext(getServletContext());
		WebApplicationContext wac = null;

		if (this.webApplicationContext != null) {
			// A context instance was injected at construction time -> use it
			wac = this.webApplicationContext;
			if (wac instanceof ConfigurableWebApplicationContext) {
				ConfigurableWebApplicationContext cwac = (ConfigurableWebApplicationContext) wac;
				if (!cwac.isActive()) {
					if (cwac.getParent() == null) {
						cwac.setParent(rootContext);
					}
					//容器加載
					configureAndRefreshWebApplicationContext(cwac);
				}
			}
		}
		if (wac == null) {
			wac = findWebApplicationContext();
		}
		if (wac == null) {
			wac = createWebApplicationContext(rootContext);
		}

		if (!this.refreshEventReceived) {
			synchronized (this.onRefreshMonitor) {
				onRefresh(wac);
			}
		}

		if (this.publishContext) {
			// Publish the context as a servlet context attribute.
			String attrName = getServletContextAttributeName();
			getServletContext().setAttribute(attrName, wac);
		}

		return wac;
	}

看到這裏想你也應該明白了，首先從ServletContext中拿到父容器，然後設置到當前容器的parent中，實現了父子容器的組織，而這樣設計好處我想也是很清楚的，子容器目前裝載的都是MVC的配置和Bean，簡單點說就是Controller，父容器中都是Service，Controller是依賴於Service的，如果不構建這樣的層級關係並優先實例化父容器，你怎麼實現Controller層的依賴注入成功呢？

總結

本篇結合之前的文章，分析了SpringMVC零XML配置的實現原理，也補充了之前未分析到父子容器關係，讓我們能從細節上更加全面的理解SpringIOC的實現原理，相信看完本篇對於SpringBoot的實現你也會有自己的想法。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨，RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※回頭車貨運收費標準